MAIN74  Euclids algorithm revisited
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 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 seperate line.
Example
Input: 1 1 Output: 2
Explaination: (1,1) is the required pair.
hide comments
ameyanator:
20180323 23:13:52
Nice problem. Reduces to Matrix Exponentiation and Fibonacci Sequences :P


NIKHIL KUMAR SINGH:
20170116 18:10:58
xpshekhar > spoiler :/ :/ :/ 

Akul Goel:
20161228 21:30:01
take care of the boundary case(s). took me almost 2 hours to find my mistake. 

Govind Lahoti:
20160126 20:06:41
Awesome Problem! Learnt a lot, made my day :) 

MAYANK NARULA:
20151228 13:32:42
a >= b was an important one !!! 

xpshekhar:
20151225 23:55:00
nice question and concept.


Adhitya Kamakshidasan:
20140527 22:04:40
Nice question. Learnt a new algorithm! 

:(){ :: & };::
20130912 15:55:37

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