题目背景

洛谷的试题为民间回忆版，仅保证题意相同。试题呈现形式、样例、数据范围可能存在差异。

题目描述

给定一个包含 $n$ 个正整数的序列 $A = [a_1, a_2, \dots, a_n]$。

你需要从中找出一个子序列，使得该子序列中任意两个不同元素的乘积都是一个完全平方数。

你的任务是求出满足条件的最长子序列的长度。

提示：

• 子序列：从原序列中删除零个或多个元素，其余元素保持原有顺序得到的序列。例如，$[2, 3, 18]$ 是 $[2, 8, 3, 18, 12]$ 的一个子序列。
• 完全平方数：一个整数，它可以表示为另一个整数的平方。例如，36 是一个完全平方数，因为 $36 = 6^2$。

输入格式

输入共两行。

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

第二行包含 $n$ 个用空格隔开的正整数 $a_1, a_2, \dots, a_n$，表示序列中的元素。

输出格式

输出一个整数，表示满足条件的最长子序列的长度。

5
2 8 3 18 12

3

提示

样例解释

我们可以找到一个满足条件的子序列 $[2, 8, 18]$，其长度为 3。

数据范围与约定

对于 100% 的数据，满足 $1 \le n \le 10^5$，$1 \le a_i \le 10^{7}$。