## MAIN74 - Euclids algorithm revisited

no tags

Consider the famous euclid algoithm to calculate the GCD of two integers (a, b):

```int gcd(int a, int b) {
while (b != 0) {
int temp = a;
a = b;
b = temp % b;
}
return a;
}```

for input (7, 3) the 'while' loop will run 2 times as follows: (7, 3) => (3, 1) => (1, 0)

Now given an integer N you have to find the smallest possible sum of two non-negative integers a, b (a >= b) such that the while loop in the above mentioned function for (a, b) will run exactly N times.

### Input

First line of input contains T (1 <= T <= 50) the number of test cases. Each of the following T lines contains an integer N (0 <= N <= 10^18).

### Output

For each test case print the required answer modulo 1000000007 in a seperate line.

### Example

```Input:
1
1

Output:
2```

Explaination: (1,1) is the required pair.

 < Previous 1 2 Next > selfcoder24: 2019-05-26 06:20:40 Finally AC after 6WA. Because of silly mistake. Learnt lots of things. selfcoder24: 2019-05-26 06:09:50 Can any one let me know whats wrong in my code? https://ideone.com/0okOZI cyber_wizard: 2019-04-25 19:37:06 Last edit: 2019-04-25 19:37:51 deepak097: 2019-04-19 16:03:40 Easy peasy :) dheeraj2806: 2018-08-09 20:19:11 NIce Question. ameyanator: 2018-03-23 23:13:52 Nice problem. Reduces to Matrix Exponentiation and Fibonacci Sequences :P PS N=0 is an Edge case! Last edit: 2018-03-23 23:14:31 NIKHIL KUMAR SINGH: 2017-01-16 18:10:58 xpshekhar --> spoiler :/ :/ :/ Akul Goel: 2016-12-28 21:30:01 take care of the boundary case(s). took me almost 2 hours to find my mistake. Govind Lahoti: 2016-01-26 20:06:41 Awesome Problem! Learnt a lot, made my day :) MAYANK NARULA: 2015-12-28 13:32:42 a >= b was an important one !!!