Twinkle loves number theory questions, but since winter is coming, her "doodle" has increased considerably so she prefers a shorter way to do everything. She has a number N , now she wants you to help her in solving a task which she thought of doing this week. Compute the sum of digits and print the summation if the the summation is prime , otherwise print the number N .

INPUT

The first line of the test case contains an integer T, denoting number of test cases. The following T lines contains one integer representing the number N.

Output

Print the answer for every test case in separate line.

Constraints

1<=T<=1000

10<=N<=10^6