文理学院程序设计在线练习


快乐数

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 175   Accepted Submission(s): 37
Problem Description

给定一个正整数,然后将其每一位数字进行平方求和后形成下一个数,循环往复,直到生成的数在前面已经出现过为止,变换结束。
例如:给定44,2个4的平方求和变成32,3的平方加2的平方等于13,1的平方加3的平方等于10,然后就是1,下面仍然是1,序列变换结束。可简单描述成:
44->32->13->10->1->1。
再例如给定2,其变换序列为:
2->4->16->37->58->89->145->42->20->4。

我们规定,给定正整数n,若最后的变换终止于数值1,则称n为“快乐数”,否则就不是。

现在的任务:给定正整数N,请你计算区间[1..N]之间有多少个“快乐数”。

Input

测试数据有多组,首先输入测试的组数T (0<T<=20),然后是T组测试数据;每组测试输入一个正整数N(1 <= N <= 5,000,000)。

Output

对于每组测试,请你计算区间[1..N]之间有多少个“快乐数”。

Sample Input
4
1
10
1000
10000
Sample Output
1
3
143
1442