NUMBERTH - Beautiful Roll Numbers

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 (e.g. 2), now it consists of 7 digits (e.g. 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 people you met.

Then the next n lines contains the roll of that person. Note: roll can have leading zeros (e.g. 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

Added by:Safayet
Date:2018-11-18
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2019-03-04 13:58:58
Missing constraint from problem statement :
number of digits in roll number <=7.
2018-11-24 18:11:37 [Lakshman]
Thanks @ julkas
2018-11-24 16:21:27 [Lakshman]
I really not getting how the answer is 1336 for 1276543.
I have below assumption please correct me if I am wrong.
1. Find all substring
2. For all substring find all permutation which is prime.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.