时间限制：1.0 s

内存限制：512.0 MB

题面描述

小杨认为他的幸运数字应该恰好有两种不同的质因子，例如：

• 12 = 2×2×3，质因子为2、3，恰好两种，属于幸运数字
• 30 = 2×3×5，质因子为2、3、5，不符合要求，不属于幸运数字

现有n个正整数，需要判断每个正整数是否是小杨的幸运数字。

输入格式

第一行包含一个正整数n，代表正整数个数。 之后n行，每行一个正整数。

输出格式

输出n行，对于每个正整数，如果是幸运数字输出1，否则输出0。

样例1

输入

3
7
12
30

输出

0
1
0

样例解释

• 7的质因子只有7，仅1种，不符合要求
• 12的质因子为2、3，共2种，符合要求
• 30的质因子为2、3、5，共3种，不符合要求

数据范围

全部数据满足：1 ≤ n ≤ 10^4，每个正整数a_i满足 2 ≤ a_i ≤ 10^6。