• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

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