5347 - 数论：威尔逊定理：求和

Input

The first line contains the number of queries t (t <= 10^6). Each query consist of one natural number n (1 <= n <= 10^6).

Output

For each n given in the input output the value of Sn.

Examples

Input

13 
1 2 3 4 5 6 7 8 9 10 100 1000 10000

Output

0 1 1 2 2 2 2 3 3 4 28 207 1609

Source

hdu2973 YAPTCHA

Time Limit 2 seconds
Memory Limit 128 MB
Discuss Stats
上一题 下一题