+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
Consider the following algorithm:
```
function gcd(a, b):
if b is 0:
return a
return gcd(b, a % b)
```
We want to create a test to evaluate the performance of this program. For each test, you need to provide two integers $a$ and $b$ such that $1 \le a, b \le n$ and this algorithm has the maximum number of `gcd` function calls.
# ورودی
The first line contains an integer $t$, representing the number of test cases.
$$1 \leq t \leq 10^5$$
In each test case, there is a single integer $n$.
$$1 \leq n \leq 10^{18}$$
# خروجی
For each test case, print the maximum number of function calls.
# مثالها
## ورودی نمونه ۱
```
5
1
2
3
4
5
````
## خروجی نمونه ۱
```
2
3
4
4
5
````