A number is called polite if it can be written as a sum of some (at least two) consecutive positive integers. For example, 6 (1+2+3) is a polite number while 4 is not. Politeness of a number is the number of ways it can be expressed as sum of consecutive positive integers. For example 6 (1+2+3) has a politeness of 1 while 18 (5+6+7 = 3+4+5+6) has a politeness of 2. Obviously, non polite number has a politeness of 0.

You are given a politeness P, you have to find out the smallest number that has the politeness P.

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a line containing an integer P (0 ≤ P ≤ 10¹²).

For each case, print the case number and the integer that has the politeness P. If there are several integers having politeness P, choose the smallest one. As the integer can be big; print the integer modulo 1000000007 (10⁹ + 7).

For case 7, 1003917915 is the smallest number with politeness 511, so the result is (1003917915 modulo 1000000007), which is 3917908.