{"raw_statement":[{"iden":"background","content":"洛谷的试题为民间回忆版，仅保证题意相同。试题呈现形式、样例、数据范围可能存在差异。"},{"iden":"statement","content":"给定一个包含 $n$ 个正整数的序列 $A = [a_1, a_2, \\dots, a_n]$。\n\n你需要从中找出一个**子序列**，使得该子序列中任意两个不同元素的乘积都是一个**完全平方数**。\n\n你的任务是求出满足条件的**最长**子序列的长度。\n\n**提示：**\n*   **子序列**：从原序列中删除零个或多个元素，其余元素保持原有顺序得到的序列。例如，$[2, 3, 18]$ 是 $[2, 8, 3, 18, 12]$ 的一个子序列。\n*   **完全平方数**：一个整数，它可以表示为另一个整数的平方。例如，36 是一个完全平方数，因为 $36 = 6^2$。"},{"iden":"input","content":"输入共两行。\n\n第一行包含一个整数 $n$，表示序列的长度。\n\n第二行包含 $n$ 个用空格隔开的正整数 $a_1, a_2, \\dots, a_n$，表示序列中的元素。"},{"iden":"output","content":"输出一个整数，表示满足条件的最长子序列的长度。"},{"iden":"note","content":"### 样例解释\n\n我们可以找到一个满足条件的子序列 $[2, 8, 18]$，其长度为 3。\n\n### 数据范围与约定\n\n对于 100% 的数据，满足 $1 \\le n \\le 10^5$，$1 \\le a_i \\le 10^{7}$。"}],"translated_statement":null,"sample_group":[["5\n2 8 3 18 12","3"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}