The Roll Numbers In IUT(International University Of Technology) got bigger in size time to time. For example , once upon a time it only consisted of 1 digit(eg. 2), now it consists of 7 digits(eg. 1741050). There was a reunion for all the IUTians recently where you met many peoples. As you are an introvert, Your seniors have given you a simple task so that you can become more social. The task is You'll have meet n people and ask their roll and then you'll have to talk with him minimum of m minutes. Here m is the beauty value of his roll.

Beauty value of a roll is the number of different prime numbers that can be generated by taking some digits from the roll and shuffling them. For example if the roll is 17, the beauty value is 3, because the only primes can be generated from this are 7,17,71.

Input

First line contains an integer 0<n<250, number of peoples you met.

Then the next n line contains the roll of that person. [Note:Roll can have leading Zero's(eg. 011)]

Output

For each person in a new line print the minimum number of minutes you had to talk to him.

Example

Input:

4

17

5

011

1276543
Output:

3

1

2

1336