古罗马哲学家塞内卡（Seneca）是未来皇帝尼禄（Nero）的老师。尼禄曾问他数字能有多大。塞内卡回答说，有些数字大到连罗马最聪明的人也无法想象；例如，通过将大于 1 的普通罗马数字相乘而得到的数字。为了避免可能产生的歧义，尼禄决定只有能以这种形式唯一表示的整数才被计算在内。

现在，一位现代艺术家决定创作一个献给尼禄和塞内卡的装置艺术，并希望在其中使用一些不超过 $10^{18}$ 的正整数。但他希望确保这些数字可以唯一地表示为一个或多个大于 1 的罗马数字的乘积（更正式地，如果两种表示作为多重集是相同的，则它们被视为同一种表示，例如表示 $4 \cdot 2$ 和 $2 \cdot 4$ 是相同的表示）。

任何严格小于 4000 的正整数（且仅有这些数）在罗马数字中都有唯一的表示；其他书写罗马数字的规则对所有参赛者来说都是众所周知的，因此为了简练起见，这里不再提供。

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 2 \cdot 10^5$) —— 测试用例的数量。

接下来的 $t$ 行中，每行描述一个测试用例，包含一个需要检查的整数 $n$ ($2 \le n \le 10^{18}$)。

输出格式

对于每个询问，如果该数字可以唯一地表示为大于 1 的罗马数字的乘积，则在单独的一行中打印 1，否则打印 0。

样例

输入 1

4
2024
2025
2026
2027

输出 1

0
0
0
1