SorbonneUniversity8

A positive integer X is a comet number if there exists 5 positive integers A B C D E such that:

• A + B + C + D = X
• A + E, B - E, C * E, and D / E are pairwise equal, meaning A + E = B - E = C * E = D / E

Kanata gave Suisei N positive integers A_i for 1 ≤ i ≤ N.

Suisei would like to know whether A_i is a comet number or not.

Input

The first line contains an integer N.

The next N lines contain an integer A_i.

Output

Print N lines.

The i-th line contains the string "YES" (without quotes) if A_i is a comet number and "NO" (without quotes) otherwise.

Example

Input:
4
8
1
69
128

Output:
YES
NO
NO
YES

Explanation

8 is a comet number as there exists a valid quintuple (A, B, C, D, E) = (1, 3, 2, 2, 1).

128 is a comet number as there exists a valid quintuple (A, B, C, D, E) = (31, 33, 32, 32, 1).

Constraints

1 ≤ N, A_i ≤ 10⁵