Let be the set of prime numbers less than .
Find the number of subsets of , the sum of whose elements is a prime number. Print this number modulo . You should find this number for several values of .
Input Format
The first line of input contains integer number of values of .
The second line of input contains values of separated by spaces.
Constraints
Output Format
Print numbers separated by space your answers in corresponding order.
Sample Input 0
2
10 4
Sample Output 0
7 3
Explanation 0
There are four prime numbers under : , , and . There are exactly seven ways to choose a subset with prime sum: , , , , , , . Only three of these subset consist of numbers under .