Daenerys Targaryen has come into possession of a lot of dragons lately. She desperately wants to rule over Westeros with the help of these dragons and become Queen of the Seven Kingdoms. But Tyrion Lannister, her advisor, is a calculative man. He wants to measure the power of each dragon before launching a full fledged attack on King's Landing, the capital of Westeros. This is making Daenerys impatient.

Coming to the dragons, they are very ancient beings but love maths. They have their ids numbered as 1,2,3.. and so on. They have a unique way of choosing friends among themselves, two dragons with ids x and y will be friends if and only if gcd(x,y)=1. A function is defined using this property :

F(n) = total number of friends of dragon 'n' who have id <= n.

eg : F(6) = 2 because only '1' and '5' are the dragons who are friends with dragon '6' and have their id <= 6. F(1) = 1, the dragon '1' is its own friend :( .

Each dragon gets its power from all the dragons having lower id than itself in the following way :

POWER(n) = F(n-1)xF(n-2)xF(n-3).....xF(1).

POWER(1) = 1.

You are Ser Jorah, the friendzoned knight, and this is your last chance to woo Daenerys and get out of this zone. Calculate the power of dragons quickly before Tyrion does it. The power of some dragons may be too large, so just print POWER(n) modulo 10^9+7.

You will be given T - number of testcases, and for each testcase a number n (id of dragon). For every testcase, you need to print the power of the dragon, as explained above, in a separate line.

Constraints :

1<=T<=10^6

1<=n<=10^6