I

Politeness Input: Standard Input Output: Standard Output

A number is called polite if it can be written as a sum of some consecutive positive integer. 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 integer. For example 6(1+2+3) is 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

The first line of input will indicate the number of test cases T (T <= 1000). Each of the following T lines will contain a non negative integer number P (P < 10^12) indicating the desired politeness.

Output

For each line of input you have to produce one line of output that will contain number that has a politeness of P. If there is more than one number having that politeness choose the smallest one. If there is no such number print impossible. If the number is greater than 1000000007 print the number mod 1000000007.

Sample Input Output for Sample Input

3 0 1 5

1 3 45

---

Problemsetter: Towhidul Islam Talukder, Special Thanks: Jane Alam Jan