说明

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

▶ 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。

▶然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。

▶如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

输入格式

输入的第一行是一个整数 $t$ ,表示有 $t$ 组数据。

接下来有 $t$ 行，每行一个整数 $n (1 \le n \le 10^8)$

输出格式

对于每个整数 n ，对应输出一行：如果 n 是 快乐数 就返回 true ；不是，则返回 false

样例

2
19
116

true
false

提示

样例解释：

比如116  按规则生成的数依次是：116 38 73 58 89 145 42 20 4 16 37 58 （58出现重复）

所有的数运算到最后归结于两种情况：

• 收敛于1
• 陷入数字循环
  

在判断过程中如何避免陷入数字循环而导致程序死循环，在此我们在这里可以使用弗洛伊德循环查找算法。

这个算法是两个奔跑选手，一个跑的快，一个跑得慢。在龟兔赛跑的寓言中，跑的快的称为 “乌龟”，跑得快的称为 “兔子”。

不管乌龟和兔子在循环中从哪里开始，它们最终都会相遇。这是因为兔子每走一步就向乌龟靠近一个节点（在它们的移动方向上）。

如下图所示：

我们不是只跟踪链表中的一个值，而是跟踪两个值，称为快跑者和慢跑者。在算法的每一步中，慢速在链表中前进 1 个节点，快跑者前进 2 个节点。

如果 n 是一个快乐数，即没有循环，那么快跑者最终会比慢跑者先到达数字 1。

如果 n 不是一个快乐的数字，那么最终快跑者和慢跑者将在同一个数字上相遇。