POLCONST  Constructible Regular Polygons
The investigation of which regular polygons can be constructed only with compass and straightedge is a classical problem in mathematics. Triangle, square, hexagon can easily be constructed, but, can we construct a regular heptagon? It was the German mathematician Gauss (17771855) who first proved that one could construct a 17sided regular polygon and later, in one the of the most beautiful math works of all time (Disquisitiones Arithmeticae, 1798), he gave sufficient conditions to decide which regular polygons can be constructed.
Input
In the first line, an integer T<50000 representing the number of test cases; then, T integer numbers representing the number of sides of a nondegenerated regular polygon, up to 1000000 (10^6).
Output
Print “Yes” if the regular polygon can be constructed with compass and straightedge or “No” otherwise.
Example
Input
5
5
6
7
8
9
Output
Yes
Yes
No
Yes
No
If you have any question, you can ask in the forum.
hide comments
shantanu tripathi:
20150822 21:30:36
done using bs :D 

[Mayank Pratap]:
20150729 15:51:19
Revised many things and learnt some new maths ... :) 

Mani Soni:
20150530 06:02:32
learned about fermat numbers by this question..Good question 

TUSHAR SINGHAL:
20150323 18:47:43
my 50th ac :)


praveen123:
20140128 13:45:00
I liked the problem very much.


Alexandre Henrique Afonso Campos:
20140128 13:45:00
The "nondegenerated" part is just a fancy way to say that all the numbers are bigger than 2 (n>2, because the minimum number of sides for a polygon like this is 3).

Added by:  campos20 
Date:  20131223 
Time limit:  1s2s 
Source limit:  1000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Classical math. 