小杨认为他的幸运数字应该恰好有两种不同的质因子，例如，12=2*2*3的质因子有2、3 ，恰好为两种不同的质因子，因此12是幸运数字，而 30=2*3*5的质因子有2、3、5 ，不符合要求，不为幸运数字。小杨现在有n个正整数，他想知道每个正整数是否是他的幸运数字。

第一行包含一个正整数n ，代表正整数个数。之后n行，每行一个正整数。
对于全部数据，保证有 1<=n<10000，每个正整数ai满足2<=ai<=1000000 。

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

GESP五级