SPOJ POLCONST

Problem link: SPOJ Problem Set (classical): 17707. Constructible Regular Polygons

As stated in the problem description, you are required to utilize this page. As there are only 5 Fermat Primes, you can easily do a pre-processing up to 10⁶ in constant time (2⁵×5) and answer each query in O(1).