小杨认为他的幸运数字应该恰好有两种不同的质因子，例如，12=2*2*3的质因子有2, 3，恰好为两种不同的质因子，因此12是幸运数字，而30=2*3*5的质因子有2，3，5，不符合要求，不为幸运数字。

小杨现在有n个正整数，他想知道每个正整数是否是他的幸运数字。

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

之后n行，每行一个正整数。

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

7的质因子有7，只有一种。

12的质因子有2，3恰好有两种。

30的质因子有2，3，5，有三种。

数据范围：

对于11/13的数据，保证有1≤ n ≤ 10^4，每个正整数ai满足2≤ai≤10^6；

对于全部数据，保证有1≤ n ≤ 10^5，每个正整数ai满足2≤ai≤10^9。

拿到92分就可以了，有兴趣的同学可以冲刺一下100分。

GJ2024