Problem E
Square
Input: Standard Input

Output: Standard Output

 

Given n integers you can generate 2n-1 non-empty subsets from them. Determine for how many of these subsets the product of all the integers in that is a perfect square. For example for the set {4,6,10,15} there are 3 such subsets. {4}, {6,10,15} and {4,6,10,15}. A perfect square is an integer whose square root is an integer. For example 1, 4, 9, 16,…. .

 

Input

 

Input contains multiple test cases. First line of the input contains T(1≤T≤30) the number of test cases. Each test case consists of 2 lines. First line contains n(1≤n≤100) and second line contains n space separated integers.  All these integers are between 1 and 10^15.  None of these integers is divisible by a prime greater than 500.

 

Output

 

For each test case output is a single line containing one integer denoting the number of non-empty subsets whose integer product is a perfect square. The input will be such that the result will always fit into signed 64 bit integer.

 

Sample Input                              Output for Sample Input

4

3

2 3 5

3

6 10 15

4

4 6 10 15

3

2 2 2

0

1

3

3

 

Problemsetter: Abdullah al Mahmud

Special Thanks to: Manzurur Rahman Khan