PEG Test - Halloween 2014

It's raining tonight, so your trick-or-treating night has already gone off to a bad start. To make it worse, you've accidentally stumbled upon the house of Mr. Chan, your math teacher. He holds out a bucket of uncooked white rice to offer to you. You take a look and think "beats me, I'm Asian so I ain't even mad." Just as you are about to reach out and grab a handful, Mr. Chan retracts the bucket and says "Not so fast! You have to solve my puzzle first."

On a sticky note, Mr. Chan gives you a list of ~N~ ~(1 \le N \le 10)~ positive integers ~a_1, a_2, \dots, a_N~. He tells you that all ~N~ integers are relatively prime with respect to each other. Two integers are considered relatively prime if their greatest common divisor is ~1~. You examine the list and say "wait a minute, these numbers aren't relatively prime!" He widened his grin, and said "Ahh, but they are. I simply didn't tell you what bases they're given in! Now it's your job to tell me what bases each number could be in."

Input Specification

Line ~1~ will contain the integer ~N~, specifying the number of integers to follow.
Line ~2~ will contain the positive integers ~a_1, a_2, \dots, a_N~, each no more than ~9~ digits long. However, the base of each number will be unknown. All numbers will be given in base between ~2~ and ~10~, inclusive.

Output Specification

The output should contain ~N~ lines. Line ~i~ should contain a single integer between ~2~ and ~10~, specifying the base that you think the number is represented in. Assuming your set of bases is correct, for any pair of numbers (after they are converted from your bases to base-~10~) should be relatively prime.
It is guaranteed that a solution will exist. If multiple valid solutions exist, you may output any one.

Sample Input

3
135 75 200

Sample Output

6
8
3

Explanation

~135_6 = 59~.
~75_8 = 61~.
~200_3 = 18~.
The numbers ~59~, ~61~, and ~18~ are all relatively prime, so this is a valid solution.