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.


hide comments
smap: 2020-10-06 19:50:38

This article helped me a lot : https://www.cut-the-knot.org/blue/LamesTheorem.shtml

You can read the part which is about Knuth's deduction

Last edit: 2020-10-06 19:52:36
horro: 2020-07-28 20:52:10

Lames Theorem, edge cases: n=0 and n=1; also try spoj problems:FIBOSUM,RABBIT1

rupok_03: 2020-06-20 13:34:22

be carefull about negative value for test case
1
1000000000001

hitesh_1711: 2020-05-13 00:27:44

Last edit: 2020-05-14 03:15:11
acodc: 2020-05-05 20:50:13

Nice problem.

itssanat: 2020-04-20 12:08:07

beware of n=0, cost me 3WAs .

dilshod_imomov: 2019-11-09 16:19:57

good question!

Last edit: 2019-11-09 16:20:39
adithyabhat_99: 2019-09-23 20:11:50

Great question, leart a whole another concept.
Binary exponentiation and matrix exponentiation :)
Thank you for this question

swag3301: 2019-07-28 16:51:31

Use Lame's Theorem ! EZ

selfcoder24: 2019-05-26 06:20:40

Finally AC after 6WA. Because of silly mistake. Learnt lots of things.


Added by:Mahesh Chandra Sharma
Date:2011-03-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem used for NSIT-IIITA main contest #7