Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Concatenation of Perfect Squares

Limits: 2s, 256 MB

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.

Samples

InputOutput
3
1259
33
169
Yes
No
Yes

Authors
Discussion
Submit

Login to submit