Zucky has a frog Abby. Abby is very hungry and Zucky decides to feed it by playing a little game. Abby is a special frog which can jump as far as it wants but has a special pattern: He starts at the point 0.
In his first turn, he can make a jump of 1 unit. Now for all consequent turns, if the frog is currently at a distance x (from the start), his jump will take him x units forward. Given a leaf at a distance N , you have to find if the frog can reach that leaf or not.

Input

The first line of the input contains an integer T denoting the number of test cases.
Each test case is in a separate line and contains a non-negative integer N .

Output

For each test case, output a single line containing True if the frog can reach that pillar and print False otherwise.

Constraints

1 ≤ T ≤ 10^5
0 ≤ N ≤ 10^18

Example
Input:
1
1

Output:
True

见题面

见题面