#8307. 「BROI Round 1」追梦启程 普及−

给定一个整数 ，你可以进行多次操作，每次可以进行两种操作中的一种，询问 能不能变为 。

称 为 的位数（例如 的位数为 ， 的位数为 ）。

操作（当 才能执行）：

• .把 的某两位数字调换位置。
• .选定一个 （）,把 从高位第 个到第 个数字删去。

第一行，一个整数 ，表示数据组数。

接下来 行，每行一个正整数 。

对于每组数据，如果可以把 变为 ，输出 1，否则输出 0。

样例输入

5
6
19
8877
114514
1919810

样例输出

0
1
0
1
1

对于 的数据，。

对于 的数据，。

对于 的数据，。