# UVa 11542 - Square

## contents

Given n integers you can generate $2^{n} - 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.

## Solution

x1 = 0 表示第一個數字如果不選，x1 = 1 則表示選。

$$a_{1}x_{1} + a_{2}x_{2} + ... = even \quad for \quad prime \quad 2 \\ b_{1}x_{1} + b_{2}x_{2} + ... = even \quad for \quad prime \quad 3 \\ ...$$