The task is to output whether a given number, N, can be expressed as a sum of distinct factorials.

For example, 9 = 1! + 2! + 3!, but 11 can never be expressed as a sum of distinct factorial.

Note that 0! and 1! are distinct factorials even if they have the same value.

Input

First line denotes the number of test cases T.

Then follows T lines, each containing a single non-negative integer N.

Output

Output T lines each containing a "YES" if N can be expressed as a sum of distinct factorials or "NO" if it can't.

T <= 10000

N <= 1000000

Example

Input:
3
9
8
11

Output:
YES
YES
NO

Explanation for Case 2

0! + 1! + 3! = 8