ADAGIFT - Ada and Birthday

no tags 

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.

Input

The first line contains an integer 1 ≤ T ≤ 100

Each of the next N lines contains a number 1 ≤ A < 1030

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: 2017-06-15 11:25:41

@[Rampage] Blue.Mary: You was right, there was a huge mistake in input data.
So firstly sorry for your time you spend over it :/
Secondly thank you for finding it!
Thirdly it shall be OK now and your solution shall get AC!

**I'm almost sure none leading zeroes are in input!

Thank you & Have nice day!!

Last edit: 2017-06-15 11:26:35

Added by:morass
Date:2017-06-15
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All