Chef and Square Set

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef is teaching his students about properties of integers. Today he is teaching them about numbers which are squares of some number, e.g. 1, 4, 9, 16, 25 etc. These numbers are said perfect squares.
He gave his students the following task as homework. He gives an array a consisting of n positive integers. He calls the array w0w if for every pair of indices i, j, the product a_{i} * a_{j} is a perfect square.
Chef wants you to make this array w0w. For achieving this, you can pick any integer a_{i} and can multiply it by any prime number. You can perform this operation several times, even multiple times on the same number. Find out the minimum number of operations that you will require.
Input
The first line of the input contains an integer T denoting the number of the test cases.
The first line of each test case will contain an integer n denoting number of elements in array a.
The next line will contain n space separated integers denoting elements of array a.
Output
For each test case, output a single integer corresponding to minimum number of operations required to make array w0w.
Constraints
 1 ≤ T, n, a_{i} ≤ 10^{6}
 1 ≤ Sum of n over all test cases in a single test file ≤ 10^{6}
Subtasks
Subtask #1: (10 points)
 1 ≤ T, n, a_{i} ≤ 10^{5}
 a_{i} is prime.
 1 ≤ Sum of n over all test cases in a single test file ≤ 10^{5}
Subtask #2: (20 points)
 1 ≤ T, n, a_{i} ≤ 10^{6}
 a_{i} is prime.
 1 ≤ Sum of n over all test cases in a single test file ≤ 10^{6}
Subtask #3: (30 points)
 1 ≤ T, n, a_{i} ≤ 10^{5}
 1 ≤ Sum of n over all test cases in a single test file ≤ 10^{5}
Subtask #4: (40 points)
 Original Constraints
Example
Input: 3 3 2 2 2 3 1 2 2 3 2 4 6 Output: 0 1 2
Explanation
Example case 1. If you multiply any pair of integers in the array, the product is 4, which is square. So, the array is w0w already.
Example case 2. You can multiply the first number by 2, then the array will become w0w. So the minimum number of operations required will be 1.
Author:  admin2 
Tester:  animesh_f 
Tags  admin2 ltime42 numbertheory prime 
Date Added:  23112016 
Time Limit:  1.5 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions