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 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.
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.
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