Project Euler #77: Prime summations

_{This problem is a programming version of Problem 77 from projecteuler.net}

It is possible to write ten as the sum of primes in exactly five different ways:

You are given , in how many ways can be written as sum of 1 or more primes?

Input Format

First line of the input contains , which is number of testcases.
Each testcase contains .

Constraints

Output Format

Print the output corresponding to each testcase on a new line.

Sample Input

2
5
10

Sample Output

2
5