#129. 陈老板的餐厅

陈老板的餐厅

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<=601<=n<=60。

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

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

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

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