# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Plus Ultra!!

By raihan.raka · Limits 1s, 512 MB

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 —

1. A student can sit anywhere he/she wants, if there's no one else in the class room.

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

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

InputOutput
3
2
4
5

0
3
6


*It is not necessary to maximize number of students in a seating arrangement

### Statistics

92% Solution Ratio

YouKnowWhoEarliest, 6M ago

YouKnowWhoFastest, 0.0s

Sara_HasanLightest, 0 B

YouKnowWhoShortest, 765B