Team ISTE is very obsessed with prime numbers. They always do their jobs in prime numbers. Even the present ongoing event PRODYOGIKI 2K14 is a 7 day event which is again a prime number. To test their newly selected students, ISTE asks them to sum the prime numbers. Your task is to input a number N, and to sum up the first N prime numbers. As this sum can get very large, you have to output the sum in terms of modulo 1009.

INPUT: First line of input consists of number 'T' denoting the number of test cases. Next 'T' lines consists of single number denoting the number 'N'.

OUTPUT: You have to output in a single line the sum of the first N prime numbers.