三重利刃 题目描述 Riku 正在准备补考。 她记得在期末前 Rio 告诉过她，一个序列如果是“摇滚的”，当且仅当其满足下面两个条件： 这个序列所有长度为奇数的子序列的乘积不是完全平方数； 这个序

三重利刃

题目描述

Riku 正在准备补考。vpK100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

她记得在期末前 Rio 告诉过她，一个序列如果是“摇滚的”，当且仅当其满足下面两个条件：vpK100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

这个序列所有长度为奇数的子序列的乘积不是完全平方数；vpK100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
这个序列所有长度为偶数的子序列的乘积是完全平方数。

Tsubaki 正在为 Riku 补习，她给出一个长度为 n 正整数序列 a，希望 Riku 能求出一个序列中最长的“摇滚的”子序列的长度，否则她会好好教育 Riku。vpK100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

因为通过补考需要熟悉这个问题的解法，所以 Tsubaki 总共有 T 个这样的问题。而期末挂科的 Riku 自然回答不上，所以她希望你帮她对每个问题求出这个长度。vpK100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入格式

第一行一个正整数 T。vpK100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

接下来每个问题共两行。vpK100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

第一行一个整数 n，表示正整数序列 a 的长度。vpK100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

第二行 n 个用空格分隔的正整数，第 i 个数表示 ai​ 的值。vpK100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输出格式

共 T 行，第i 行输出第 i 个问题的答案。vpK100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

数据范围

对于 30%的数1≤T≤50，1≤n,∑n≤50；vpK100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
对于另外 30% 的数据，1≤n≤3，1≤ai​≤10^3；vpK100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
对于 100% 的数据，1≤T≤5⋅10^5，1≤n,∑n≤5⋅10^5，1≤ai​≤10^7。vpK100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
样例数据vpK100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入:vpK100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
3vpK100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
5vpK100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
8 12 12 16 27vpK100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
5vpK100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
7 10 18 8 1vpK100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
4vpK100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1 9 1 9vpK100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出:vpK100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
3vpK100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
2vpK100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
0