Longest Subsequence with Perfect Square Product

You are given an array of positive integers. Your task is to find the length of the longest subsequence such that when the subsequence is sorted in non-decreasing order, the product of every pair of adjacent elements is a perfect square. In mathematical terms, for any adjacent pair a and b in the sorted subsequence, the product a \times b should be a perfect square, i.e. there exists an integer k such that \( k^2 = a \times b \).

If no two elements can form such a pair, the answer should be 1 (taking any single element).

Example:

Input:  5
        1 4 16 9 25
Output: 5

inputFormat

The first line contains a single integer N (1 ≤ N ≤ 10⁵), representing the number of elements in the array.

The second line contains N positive integers separated by spaces.

outputFormat

Output a single integer which is the length of the longest subsequence such that, after sorting, the product of every adjacent pair of elements is a perfect square.

5
1 4 16 9 25

5