# Simple task Pechkin

# Simple task Pechkin

Today, bringing once again part of the bones, which he promised Sharik in riddles "Bones for Sharik" and that, as Pechkin already knew he would be a great age, the postman has decided once again to verify mathematical ability Matroskin:

- *I am here that I thought, dear friend of mine Matroskin* - flowery language from afar began its task Pechkin. - *That I brought today Sharik 9 seed.Are you there is something mentioned about the cleverest of cats, the prime number. So the question: How many different ways can be decomposed into a handful of these 9 seed, so that in each of the piles was a prime seed?*

- *Elementary, Pechkin! **Look: 9 = 2 5 2 = 2 3 2 2 = 3 3 3 = 2 7, a total of 4 ways. *- Matroskin answered quickly and proudly went to the next milking their Cows.

- *Yeah*, - thought Pechkin - *in practice, already checked that if they wanted to I could not physically pick up and bring more than 330 bones, so my zadachka really simple.*

And if you can solve the puzzle Pechkin with which so quickly mastered Matroskin?

**Input**

Input data consisted of several test cases (**t** ≤ **20**), each of which is on a separate line contains another borne Pechkin number of bones. It is known that Pechkin always brought at least 2 seeds.

**Output**

For each test case on a separate line to derive the number of such locations. Please note that changing the location of the heaps of the new method does not.

2 9 200

1 4 9845164