Mr. Zuckerberg's Age Game

Mark Zuckerberg is the founder and CEO of Facebook, which he started in his college dorm room in 2004 with roomates Dustin Moskovitz and Chris Hughes and from New York.
Zuckerberg is responsible for setting the overall direction and product strategy for the company. He leads the design of Facebook's service and development of its core technology and infrastructure. Mark studied computer science at Harvard University before moving the company to Palo Alto, California.
Earlier in life, Zuckerberg developed a music recommendation system called Synapse and a peer-to-peer client called Wirehog. However, he abandoned both to pursue new projects.
Zuckerberg attended Harvard University and studied computer science before founding Facebook.
Enough about Mr. Zuckerberg’s life story. Let’s cut to the chase. Mr. Zuckerberg considers someone talented if his/her age is divisible only by 1 or that number itself. Now Mr. Zuckerberg is tired of writing code. He wants you to find out that given someone’s age whether he/she is talented or not. I am sure you are one of them. Are you? Then go ahead, help Mr. Zuckerberg.

Input

Input will start with an integer,T (≤ 103) denoting the number of test cases. Next T line will contain one integer N (1 ≤ N ≤ 504) the age of a Person.

Output

For each case, print 1 if the person is talented and 0 if he/she is not.

Sample

Input	Output
3 101 28 10	1 0 0

Please focus on the problem carefully. Do not assume anything else.