NSITACMB - Factorial Sum

no tags 

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


hide comments
Simes: 2023-03-15 07:55:49

"...as a sum of distinct factorials" - this includes those numbers that are a sum of just one factorial.


Added by:Mukul Gupta
Date:2013-03-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64