Neel partied hard last night, forgetting that there was a test in school today. In the test, the first question was to write a set of "Special" numbers. Since Neel had no clue about Special numbers, he tried to glance over his neighbour's shoulder and managed to catch a partial glimpse of the numbers. Taking a chance, he guessed the remaining digits and submitted his paper.

Obviously, he got the numbers wrong! Write a program to determine how far off the nearest Special Number was, from his answers.

A number $p$ is a Special number if $p$ divided by the sum of its digits gives a prime number e.g. $18$ is a Special number because $18 / (1 + 8) = 2$, where $2$ is a prime number.

Read the input from STDIN and print the output to STDOUT. Do not write arbitrary strings anywhere in the program, as these contribute to the standard output and test cases will fail.

Input Format:

• In the first line of input, consists of a single integer $n$, the count of numbers written by Neel.
• Second line of input consists of $n$ space-separated numbers.

---

Output Format:

• In a single line of output, print how far off the nearest Special number was from each number.
• In case there are two Special numbers equally far off from the given number, consider the lower Special number.

---

Sample Cases

Sample Input 1:

3
17 19 20

Sample Output 1:

1 -1 1

Explanations: 3 numbers are given: $17$, $19$, and $20$.

• Nearest Special number to $17$ is $18$, hence $\implies 18 - 17 = 1$
• Nearest Special number to $19$ is $18$, hence $\implies 18 - 19 = -1$
• Nearest Special number to $20$ is $21$, hence $\implies 21 - 20 = 1$

---

Sample Input 2:

4
43 44 116 115

Sample Output 2:

-1 1 1 -1

Explanations:

• Nearest Special Number to $43$ is $42$, hence $42 - 43 = -1$
• Nearest Special Number to $44$ is $45$, hence $45 - 44 = 1$
• Nearest Special Number to $116$ is $117$, hence $117 - 116 = 1$
• Nearest Special Number to $115$ is $114$, hence $114 - 115 = -1$