504007 - YAPTCHA

Input

第一行为一个整数t(t≤1000000),表示有t组测试数据,随后t行中的每一行为一个整数n (1≤n≤1000000)。

Output

每行输出一组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
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题