小明刚刚在数学课上学习了什么是平方数，例如 25=5\times 5，则 25 是一个平方数。现在数学老师布置了一个任务：给定 n 个整数，将其中的平方数选择出来，并按照原来的先后顺序输出。这么多，又那么大的数，人工判断显然比较繁琐，学会了编程的你，请你编写一个程序帮助小明来完成这个任务。

第一行仅有一正整数 n\ (1\le n\le 100)。

第二行包含 n 个正整数（均不超过 10^6），两两之间用一个空格分隔。

输出包含若干行，每行仅有一个平方数（记得是按照输入数据的先后顺序输出啊）。

首先预处理 10^6 内 1000 个平方数，开个数组标记一下每个数是否为平方数，然后读入的 n 个数，判断下是否为平方数，若是就输出。