该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

现在有n个客人来到餐厅，以如下方式选座。

1：第一个人坐在最左边的位置。

2：第i（i>=2）个人坐在位置Ai，使得他与已经入座的人的最小距离d最远。即使得d=min（|Ai-Aj|）(j<i) 最大，若有多个位置满足条件，坐在最左边的那一个。

3：任意两个人不能相邻，即d>=2。

陈老板向你提了一个问题：至少需要多少个座位，才能满足这n个人就餐的需要？

Format

Input

第一行一个正整数T为数据组数。

接下来每行一个正整数n。

Output

对于每组数据，输出一个正整数，为最少需要的座位数。

Samples

1
4

8

1
233

489

1
1234567

3331719

Limitation

【样例解释一】

1.第一个人坐在1号位置。

2.第二个人坐在8号位置，离已经入座的所有人距离最远，d=7。

3.第三个人可以选择坐在4号或5号位置，离已经入座的所有人距离都最远，d=3，坐在最左边的4号位。

4.第四个人坐在6号位置，离已经入座的所有人距离最远，d=2。

所以，8个座位可以满足4个客人的就餐需求。

同时可以验证，7个或7个以下的座位不可以满足4个客人的需求。

【数据范围与约定】

对于第1,2,3个测试点，$1<=n<=60。$

对于第4,5,6个测试点，$1<=n<=10^5。$

对于第7,8个测试点，$1<=n<=10^{10}。$

对于第9,10个测试点，$1<=n<=10^{18}。$

对于100%的数据，1<=T<=50。