Beautiful Perfect Square Subsequence

You are given several arrays. For each array, your task is to determine the maximum length of a beautiful subsequence. A beautiful subsequence is defined as the subsequence that contains only perfect square numbers. A number \( x \) is said to be a perfect square if there exists an integer \( r \) such that \( r^2 = x \). For example, 1, 4, 9, 16, etc. are perfect squares.

The input starts with an integer \( T \) (the number of test cases). For each test case, the first integer is \( n \) representing the size of the array, followed by \( n \) integers.

Your task is to compute, for every test case, the count of perfect square numbers in the given array, and output the result on a separate line for each test case.

Note: Use appropriate methods to check for perfect squares (for instance using integer square roots) and ensure your solution handles input from standard input and outputs to standard output.

inputFormat

The first line contains an integer \( T \), the number of test cases. Each test case begins with an integer \( n \) in a new line, the size of the array. The next line contains \( n \) space-separated integers.

Example:

3
4
1 2 3 4
5
1 2 2 3 3
6
1 4 9 16 25 36

outputFormat

For each test case, output a single line with the count of perfect square numbers present in the array.

Example:

2
1
6

## sample

3
4
1 2 3 4
5
1 2 2 3 3
6
1 4 9 16 25 36

2
1
6

</p>