We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

- All Contests
- ProjectEuler+
- Project Euler #249: Prime Subset Sums

# Project Euler #249: Prime Subset Sums

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