MAIN74 - Euclids algorithm revisited

我们经常用大名鼎鼎的欧几里得算法（辗转相除法）来计算两个数的最大公约数。 对于 $(7,3)$，上述代码中的 `while` 循环将运行两次： $(7,3)\rightarrow(3,1)\rightarrow(1,0)$ 现在给你一个整数 $N(0\le N\le10^{18})$，你需要找出和最小的二元组 $(a,b)$ 满足 $(a\ge b\ge0)$ 且上面提到的代码 `while` 循环将恰好运行 $N$ 次 Translated By 飞丞

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.

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).

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

1
1

2