ADAGIFT  Ada and Birthday
Even though there is almost half a year before Ada the Ladybug's birthday, her friend already started searching for a birthday gift. As Ada is a mathematician, they decided to give her a number. They know that Ada loves numbers, which are composed by concatenation of prime numbers (at least one).
Sometime there are multiple ways to do so: for example 37 can be concatenation of "3" and "7", yet it can also be concatenation of "37" itself. The more ways, the better the number is. Ada's friends want to surprise her by as good number as possible so they want you to write a program, which could count the number of ways.
NOTE:Number with leading zeroes is a valid number (treat it as if the leading zeroes are not there)
Input
The first line contains an integer 1 ≤ T ≤ 100
Each of the next N lines contains a number 1 ≤ A < 10^{30}
Output
For each number, print the number of ways it can be written as concatenation of prime numbers.
Example Input
8 2 37 111 3737 133 1000000009 113731191937237 1111111111111111111111
Example Output
1 2 0 6 1 1 197 1
hide comments
morass:
20170911 13:18:03
@Min_25: Good day to you,


Min_25:
20170903 09:18:44
Why the answer for "202" is 1 ? IMHO, "2" + "02" is not a concatenation of primes. Last edit: 20170903 09:30:51 

morass:
20170615 11:25:41
@[Rampage] Blue.Mary: You was right, there was a huge mistake in input data.

Added by:  Morass 
Date:  20170615 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 