输入描述:

第一行输入 n(1≤n≤3*10^5) ，表示数组的长度。
第二行输入a1……an(-1000000≤ai≤1000000)
第三行输入q(1≤n≤3*10^5) ， 表示询问的次数
下面q行，每行两个整数表示查询的区间：l,r(1≤l≤r≤n)

输出描述:

对每次查询输出一行：输出1个整数 ans ，表示查询区间的两个数的乘积为完全平方数的对数。