Problem Description

ztr loves research Math.One day,He thought about the "Lower Edition" of triangle equation set.Such as $n=x^{2}-y^{2}$.

He wanted to know that ,for a given number n,is there a positive integer solutions?

Input

There are T test cases.
The first line of input contains an positive integer $T(T<=10^{6})$ indicating the number of test cases.

For each test case:each line contains a positive integer ,$n <=10^{18}$.

Output

If there be a positive integer solutions,print $True$,else print $False$

4
6
25
81
105

False
True
True
True

Hint

For the fourth case,$105 = 13^{2}-8^{2}$