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
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 !!!

xpshekhar: 2015-12-25 23:55:00

nice question and concept.
http://zobayer.blogspot.in/2010/11/matrix-exponentiation.html

Adhitya Kamakshidasan: 2014-05-27 22:04:40

Nice question. Learnt a new algorithm!

:(){ :|: & };:: 2013-09-12 15:55:37


Nice test cases,there was a fault in my fib generator but it had passed every other problem except this one.


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