题目描述

小红设计了一种"幸运编码"规则来给正整数打分。规则如下：

从右往左看一个正整数，个位为第 $1$ 位，十位为第 $2$ 位，以此类推。

• 偶数位（第 $2, 4, 6, \ldots$ 位）保持不变。
• 奇数位（第 $1, 3, 5, \ldots$ 位）做如下变换：将该位数字乘以 $7$，若结果不大于 $9$ 则变换完成；否则将结果的各位数字相加，重复此过程直到结果不大于 $9$ 为止。

变换完成后，把所有位的变换结果相加。若总和是 $8$ 的倍数，则称该正整数为幸运数。

例如，$16347$：

• 第 $1$ 位为 $7$，$7 \times 7 = 49$，$4+9=13$，$1+3=4$，变换结果为 $4$；
• 第 $2$ 位为 $4$，偶数位不变，保持 $4$；
• 第 $3$ 位为 $3$，$3 \times 7 = 21$，$2+1=3$，变换结果为 $3$；
• 第 $4$ 位为 $6$，偶数位不变，保持 $6$；
• 第 $5$ 位为 $1$，$1 \times 7 = 7$，变换结果为 $7$。

变换后各位为 $7, 6, 3, 4, 4$，总和 $7+6+3+4+4=24$，是 $8$ 的倍数，因此 $16347$ 是幸运数。

输入格式

第一行一个正整数 $N$，表示待判断的数的个数（$1 \le N \le 20$）。

接下来 $N$ 行，每行一个正整数，小于 $10^{12}$。

输出格式

输出 $N$ 行，每行一个字符：若对应正整数是幸运数则输出 T，否则输出 F。

样例

2
16347
76344

T
F

提示

提示：可以逐个输入逐个输出，不必等所有输入结束。