著名的版图游戏“卡坦岛开拓者”（Settlers of Catan）在开始时会创建一个随机的版图。该版图由六边形资源板块组成，包含五种不同的资源：粘土、木材、羊毛、粮食和矿石。为了简单起见，我们用数字 $1$ 到 $5$ 来表示它们。

然而，随机生成的版图经常会出现多个相同的资源板块相邻的情况。这让一些玩家感到困扰。因此，我们发明了一种创建游戏版图的新方法。从中心开始并向外螺旋延伸，每次向版图中添加一个新板块时，我们根据以下规则选择该板块的资源：

• 新板块的资源必须与版图上目前已有的相邻板块的资源不同；
• 如果有多种资源可选，我们选择目前在版图上出现次数最少的一种资源；
• 如果仍有多种资源可选，则选择其中编号最小的资源。

下图展示了如何向外螺旋延伸以及最先选择的资源板块。我们想知道添加到版图中的第 $n$ 个板块（从 $n = 1$ 开始）上的资源编号是多少。

输入格式

输入的第一行包含一个整数 $c$ ($1 \le c \le 200$)，表示测试用例的数量。

接下来的每个测试用例包含一行，其中有一个整数 $n$ ($1 \le n \le 10\,000$)，表示我们想知道的板块编号。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示第 $n$ 个板块的资源编号。

样例

输入样例 1

4
1
4
10
100

输出样例 1

1
4
5
5