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 .
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.
Output exactly lines with the answer modulo for the -th query on -th line.