题目描述

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

「快乐数」定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 $1$，也可能是 无限循环 但始终变不到 $1$。
• 如果这个过程 结果为 $1$，那么这个数就是快乐数。

现在给定 $T$ 组测试数据，请你对每组数据判断：如果 $n$ 是快乐数，请输出 1；否则，输出 0。

输入格式

第一行一个整数 $T$（$1 \le T \le 1000$），表示测试数据组数。
接下来 $T$ 行，每行一个整数 $n$。

• 数据范围：$1 \le n \le 2^{31} - 1$

输出格式

对于每一组输入，输出一行结果：

• 若 $n$ 是快乐数，输出 1
• 否则，输出 0

输入输出样例

3
19
2
7

1
0
1

样例解释 #1

• 第 1 组：$n = 19$
  $1^2 + 9^2 = 82$
  $8^2 + 2^2 = 68$
  $6^2 + 8^2 = 100$
  $1^2 + 0^2 + 0^2 = 1$ → 1

• 第 2 组：$n = 2$
  进入循环 $2 \to 4 \to 16 \to 37 \to 58 \to 89 \to 145 \to 42 \to 20 \to 4 \to \dots$ → 0

• 第 3 组：$n = 7$
  最终收敛到 $1$ → 1