flirly 精通数学，经常研究数学问题。对于质数这种问题更是无敌。

对于N个不同的质数P1,P2.....Pn，用这些质数作为项（允许重复），任意组成一个数列，使这个数列的任一连续项的乘积不是完全平方数。

求出这种数列的项数的最大值,flirly想知道这个值的大小，由于结果可能很大，只需要输出对一个给定正整数m取模后的结果即可。你知道这个

结果吗？ -Standard input will contain multiple data sets. Each data set consists two parts.

　For the first part, the first line is an integer N, followed by N lines. Each line contains an integer Si(Si<=32768), representing

the power of each monkey.

　For the second part, the first line is an integer M (M <= 100,000), meaning there were M times of conflicts. Then, M lines follow,

each line contains two integers x and y, which means the xth monkey has conflict with the yth monkey.