CPDUEL5A - Comet Number

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 Ai for 1 ≤ i ≤ N.

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

Input

The first line contains an integer N.

The next N lines contain an integer Ai.

Output

Print N lines.

The i-th line contains the string "YES" (without quotes) if Ai 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, Ai ≤ 105


Added by:Maximilliano
Date:2020-11-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own Problem

hide comments
2021-08-27 06:55:41 Waseem Ahmed
Thanks for the hints @@sachinverma and @robosapien
2021-01-02 19:47:33 Sachin verma
Simple maths and loop. Also, might be obvious but watch out for the "positive integers" bit, costed me few WAs.
2020-11-26 20:16:08
nice problem.. just one observation does the job. :)
2020-11-09 08:54:44 Sushovan Sen
@nadstratosfer please try to keep one successful submission per user. Otherwise it dilutes points gained for other users. It may not matter for you but it may matter for somebody else.

[NG]: The points are calculated based on number of users who got AC, not the separate submissions. Speaking of dilluting the points though, I wonder how come the first AC here was achieved by a chinese bot from another judge system...

Last edit: 2020-11-09 11:21:13
2020-11-08 17:17:18
1) Please replace Ai with X for simplicity and consistency.
2) Please explain what "A + E, B - E, C * E, and D / E are pairwise equal" means; assuming that A+E = B-E and C*E = D/E allows a quintuple (5, 9, 11, 44, 2) for X=69.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.