This problem is a programming version of Problem 203 from projecteuler.net
The binomial coefficients can be arranged in triangular form, Pascal's triangle, like this:
It can be seen that the first eight rows of Pascal's triangle contain twelve distinct numbers:
, , , , , , , , , , and .
A positive integer is called squarefree if no square of a prime divides . Of the twelve distinct numbers in the first eight rows of Pascal's triangle, all except and are squarefree. The sum of the distinct squarefree numbers in the first eight rows is .
Find the sum of the distinct squarefree numbers in the first rows of Pascal's triangle.
Since the answer can be huge, output it modulo .
Input Format
First line of each test file contains a single integer which is the number of queries per this file. lines follow each containing a single integer that is the number of the rows in the Pascal's triangle.
Constraints
Output Format
Output exactly lines with the answer modulo for the -th query on -th line.
Sample Input 0
1
8
Sample Output 0
105
Explanation 0
mod