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 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.
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.