Dynamic Programming Optimization with Convex Hull Trick
Our favorite truck driver Ramesh has become quite bored driving trucks.So to make his long tedious journey more enjoyable he decides to do the following mental activity - he chooses a number N , and finds the sum of all i such that
- 1 <= i <=N
- gcd(i,N) = i
He then gives this sum to Suresh . If the sum is double the value of N Suresh says “YES” otherwise Suresh says “NO” . One morning Suresh doesn’t turn up . So he gives Suresh’s task to you . Given the value of N , print “YES” if the above sum is twice the value of N or “NO” if otherwise .
Input
The first line of the input contains a single integer T-denoting the number of test cases.
The first and only line of each test case contains a single integer N.
Output
For each test case print “YES” or “NO” according to the conditions stated above.
Constraints
1<=T<=1000
1<=N<=106
