UA high school is one of the most prestigious schools in Japan that aims to train future heroes in an academic manner. Due to recent Coronavirus situation all over the world the school authority decided to take exams of the students differently.
First, they decided to put n sits in a row numbered 1 to n from left to right. The school authority wants their students to take their own decisions. So, they came up with some rules that will allow the students to sit according to their will, maintaining a proper distance also. The rules are as follows —
A student can sit anywhere he/she wants, if there's no one else in the class room.
A student can sit at j th sit from the left, if the rightmost student is seated at the i th sit and j-i is a prime number.
A seating arrangement is valid if total number of student in that arrangement is a prime number.
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. Now, the school authority wants to know how many valid seating arrangement is possible. As a former student of UA high and a renowned programming hero the school authority needs your help to solve this problem.
Input
The first line of the Input will contain a single integer T (T≤ 15). Each of the next T lines contains a single integer n(1≤ n ≤23), number of sits the school authority can provide.
Output
For each test case print the number of valid seating arrangements for corresponding number of sits.
Sample
| Input | Output |
|---|---|
3 2 4 5 | 0 3 6 |
*It is not necessary to maximize number of students in a seating arrangement
