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
t=input()
for i in range(t):
    n=input()
    s=0
    a=[]
    flag=0
    a.append(1)
    while(s<n):
        for j in range(len(a)-1):
            s+=a[j]
        a.append(s)
   
    
    for i in range(len(a)-1):
        flag+=a[i]
    if n==flag:
        print True
    else:
        print False