PEG Judge - Stingy Candyman

PEG Test - Halloween 2014

Problem E: Stingy Candyman

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 ≤ N ≤ 10) positive integers a₁, a₂, …, 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 Format

Line 1 contains the integer N, specifying the number of integers to follow.
Line 2 will contain the positive integers a₁, a₂, …, a_N, each no more than 9 digits long. However, the base of each numbers will be unknown. All numbers will be given in base between 2 and 10, inclusive.

Output Format

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.