Problem Description

A self-power number is a number with \( N \) digits, where the sum of the \( N \)-th powers of its digits equals the number itself. For example, \( 153 \) is a 3-digit number, and the sum of the 3rd powers of its digits, \( 1^3 + 5^3 + 3^3 = 153 \), makes \( 153 \) a self-power number; \( 1634 \) is a 4-digit number, and the sum of the 4th powers of its digits, \( 1^4 + 6^4 + 3^4 + 4^4 = 1634 \), makes \( 1634 \) a self-power number. Now, given several positive integers, please determine if they are self-power numbers.

Input Format

The first line of input is a positive integer \( M \), indicating the number of positive integers to be judged. It is guaranteed that \( 1 \leq M \leq 100 \).

Starting from the second line, there are \( M \) lines, each containing one positive integer to be judged. It is guaranteed that these integers are all less than \( 10^8 \).

Output Format

Output \( M \) lines. If the corresponding positive integer is a self-power number, output the uppercase letter \( \texttt{T} \); otherwise, output the uppercase letter \( \texttt{F} \).

Hint: You do not need to wait until all inputs are finished to output the results. You can input a number, judge it, output the result, and then proceed to the next number.

Sample Input and Output

Sample Input #1

3
152
111
153

Sample Output #1

F
F
T

Sample Input #2

5
8208
548834
88593477
12345
5432

Sample Output #2

T
T
T
F
F

见题面 Input 部分

见题面 Output 部分