题目描述

Riku 正在准备补考。

她记得在期末前 Rio 告诉过她，一个序列如果是“摇滚的”，当且仅当其满足下面两个条件：

• 这个序列所有长度为奇数的子序列的乘积不是完全平方数；
• 这个序列所有长度为偶数的子序列的乘积是完全平方数。

Tsubaki 正在为 Riku 补习，她给出一个长度为 $n$ 正整数序列 $a$，希望 Riku 能求出一个序列中最长的“摇滚的”子序列的长度，否则她会好好教育 Riku。

因为通过补考需要熟悉这个问题的解法，所以 Tsubaki 总共有 $T$ 个这样的问题。而期末挂科的 Riku 自然回答不上，所以她希望你帮她对每个问题求出这个长度。

输入格式

第一行一个正整数 $T$。

接下来每个问题共两行。

第一行一个整数 $n$，表示正整数序列 $a$ 的长度。

第二行 $n$ 个用空格分隔的正整数，第 $i$ 个数表示 $a_i$ 的值。

输出格式

共 $T$ 行，第 $i$ 行输出第 $i$ 个问题的答案。

3
5
8 12 12 16 27
5
7 10 18 8 1
4
1 9 1 9

3
2
0

数据范围

• 对于 $30\%$ 的数据，$1 \le T \le 50$，$1 \le n, \sum n \le 50$；
• 对于另外 $30\%$ 的数据，$1 \le n \le 3$，$1 \le a_i \le 10^3$；
• 对于 $100\%$ 的数据，$1 \le T \le 5 \cdot 10^5$，$1 \le n, \sum n \le 5 \cdot 10^5$，$1 \le a_i \le 10^7$。