9541: 小塔的序列

小塔是一位热爱数学的初中生，最近她在研究一些有趣的数字序列。有一天，她在整理自己的数字卡片时发现了一个有趣的问题：如何从一长串数字中找出最长的连续子序列，使得这些数字的乘积是一个完全平方数？

完全平方数是指可以表示为某个整数的平方的数，比如1(1×1)、4(2×2)、9(3×3)等。小塔觉得这个问题很有挑战性，决定编写一个程序来解决它。

给定一个数字序列 $a$，请你帮助小塔找出最长的连续子区间，使得这个子区间内所有数字的乘积是一个完全平方数。如果存在多个长度相同的子区间，选择最靠左的一个。

第一行包含一个整数 $t$，表示测试用例的数量

每个测试用例包含两行：

• 第一行一个整数 $n$，表示序列的长度
• 第二行包含 $n$ 个空格分隔的整数 aiai，表示序列中的数字

保证所有测试用例的 $n$ 之和不超过 107107

数据范围：

• 1≤t≤1051≤t≤105
• 1≤n≤1051≤n≤105
• 1≤ai≤1061≤ai≤106

对于每个测试用例，输出一行两个整数 $l$ 和 $r$，表示满足条件的最长子区间的左右端点（从1开始计数）

如果有多个长度相同的子区间，输出 $l$ 最小的一个

如果没有满足条件的子区间，输出 -1 -1