Concatenation of Perfect Squares

You are given a positive integer number. You have to determine whether this number can be represented as the concatenation of perfect square numbers. A few example follows:

1259 = '1' + '25' + '9' and

169 = '16'+ '9' or '169'

Input

Input starts with an integer T (1 <= T ≤ 50000), denoting the number of test cases. Each case contains a positive integer N (1 <= N <= 1018) .

Output

For each test case, print Yes if given number can be represented as the concatenation of perfect square numbers, otherwise print No.

Sample

Input	Output
3 1259 33 169	Yes No Yes