Alice and Bob devised a new game to play. Alice wrote an expression on the paper and started generating an array of numbers from that. She wrote the formula as

a[i] = (51 * a[i - 1] + 52) % 53 + 1

The array starts from index 1 and a[0]=1

Bob takes all the numbers from that array up to an index N also given by Alice. He makes all the subsets possible from that array. He calculates the sum of numbers in each of the subsets and finds which of the subset is prime. A subset is prime if the sum of numbers in the subset is a prime number. Bob gets boggled by the enormous size of array that Alice is generating and asking him to do this. Can you help Bob calculate the number of different prime subsets that can be made from the given array ?

Constraints

0 < T <= 100
0 < N <= 10^5

Input

It consists of T+1 lines were T is the number of test cases and N is the index of the array up to which Bob has to calculate. The array of the numbers can always be formed from the formula that Alice wrote.
Note : Array index starts from 1. Hence a[0] is not an element of the array.

Output

Print T lines each containing the number of different prime subsets that can be made from the array given.

Example

Input:
2
4
5

Output:
3
6