MAIN74  Euclids algorithm revisited
Consider the famous Euclid algorithm 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 nonnegative 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 separate line.
Example
Input: 1 1 Output: 2
Explanation: (1,1) is the required pair.
hide comments
smap:
20201006 19:50:38
This article helped me a lot : https://www.cuttheknot.org/blue/LamesTheorem.shtml


horro:
20200728 20:52:10
Lames Theorem, edge cases: n=0 and n=1; also try spoj problems:FIBOSUM,RABBIT1 

rupok_03:
20200620 13:34:22
be carefull about negative value for test case


acodc:
20200505 20:50:13
Nice problem. 

itssanat:
20200420 12:08:07
beware of n=0, cost me 3WAs . 

dilshod_imomov:
20191109 16:19:57
good question! Last edit: 20191109 16:20:39 

adithyabhat_99:
20190923 20:11:50
Great question, leart a whole another concept.


swag3301:
20190728 16:51:31
Use Lame's Theorem ! EZ 

selfcoder24:
20190526 06:20:40
Finally AC after 6WA. Because of silly mistake. Learnt lots of things. 

deepak097:
20190419 16:03:40
Easy peasy :) 
Added by:  Mahesh Chandra Sharma 
Date:  20110313 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own problem used for NSITIIITA main contest #7 