Lucky Number

Problem Description

Xiaoming invented a kind of "lucky number". For a positive integer, its even positions stay unchanged (the units digit is position $1$, the tens digit is position $2$, and so on), while its odd positions are transformed as follows: multiply the digit by $7$; if the result is not greater than $9$, use it as the transformed result; otherwise add up the digits of the result, and if that sum is not greater than $9$, use it as the transformed result; otherwise (the sum is still greater than $9$) keep adding the digits until the result is not greater than $9$, and use that as the transformed result. After the transformation, add up the digits of the transformed result; if the sum is a multiple of $8$, the original positive integer is called a lucky number.

For example, for $16347$: the $1$st digit is $7$, multiplied by $7$ gives $49$, which is greater than $9$; adding its digits gives $13$, still greater than $9$; adding again gives $4$ as the final result. The $3$rd digit is $3$, transformed to $3$. The $5$th digit is $1$, transformed to $7$. The final transformed result is $76344$, whose digit sum is $24$, a multiple of $8$. Therefore $16347$ is a lucky number.

The corresponding multiple-choice and true/false questions can be found at https://ti.luogu.com.cn/problemset/1126 .

Input Format

The first line contains a positive integer $N$, the number of positive integers to be judged. It is guaranteed that $1 \leq N \leq 20$.

The following $N$ lines, starting from line $2$, each contain one positive integer to be judged. These positive integers are guaranteed to be less than $10^{12}$.

Output Format

Output $N$ lines, indicating whether each of the $N$ positive integers is a lucky number: if yes output T, otherwise output F.

Hint: you do not need to wait for all input to finish before outputting in order; you may read a number, judge it, output the result, then read the next number.

Sample Input

2
16347
76344

Sample Output

T
F

Sample Explanation

For the first positive integer to be judged, $16347$, its odd positions are transformed while even positions stay unchanged, yielding $76344$, whose digit sum is $24$, a multiple of $8$, so it is a lucky number and T is output. For the second positive integer to be judged, $76344$: the units digit (position $1$) $4$ multiplied by $7$ gives $28$, $2 + 8 = 10$ is still greater than $9$, adding again gives $1$, transformed to $1$; the tens digit $4$ stays unchanged; the hundreds digit $3$ multiplied by $7$ gives $21$, $2 + 1 = 3$, transformed to $3$; the thousands digit $6$ stays unchanged; the ten-thousands digit $7$ multiplied by $7$ gives $49$, $4 + 9 = 13$, $1 + 3 = 4$, transformed to $4$. Combining them gives $46341$, whose digit sum is $4 + 6 + 3 + 4 + 1 = 18$, not a multiple of $8$, so it is not a lucky number and F is output.

Constraints

• $1 \leq N \leq 20$
• Each positive integer to be judged is $< 10^{12}$