Project Euler #249: Prime Subset Sums

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 .