Background

美鼠王---文轩拥有一根别人非常羡慕的可长可短的如意金箍棒.

Description

这一天, 文轩又玩起了他的金箍棒, 他在想, 金箍棒还可以怎么玩呢?

我们可以把金箍棒看作是一段一段组成的, 每一段上都有一个0到9的数字.

他可以通过变换将金箍棒变形.

变换的方式为: 每一次将各个数字平方之后相加, 得到的和就是新的金箍棒状态.

比如19->82->68->100->1, 可以看到最终金箍棒变换为1.

文轩现在想知道, 金箍棒最终是否可以变换为1?

Format

Input

第1行一个数字t, 表示有t次计算

接下来t行, 每行一个正整数, 表示金箍棒的初始状态

Output

一共输出t行, 如果最终金箍棒可以变换为1, 则输出 true , 否则输出 false

Samples

1
19

true

2
1463
790

false
true

Limitation

1s, 1024KiB for each test case.

$1 \le t \le 1000$

$1 \le n \le 10^{1000}$