K - Time Complexity


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

Consider the following algorithm:

function gcd(a, b):
    if b is 0:
        return a
    return gcd(b, a % b)
Plain text

We want to create a test to evaluate the performance of this program. For each test, you need to provide two integers aa and bb such that 1a,bn1 \le a, b \le n and this algorithm has the maximum number of gcd function calls.

ورودی🔗

The first line contains an integer tt, representing the number of test cases.

1t1051 \leq t \leq 10^5

In each test case, there is a single integer nn.

1n10181 \leq n \leq 10^{18}

خروجی🔗

For each test case, print the maximum number of function calls.

مثال‌ها🔗

ورودی نمونه ۱🔗

5
1
2
3
4
5
Plain text

خروجی نمونه ۱🔗

2
3
4
4
5
Plain text
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.