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 1015. 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 4 3 235 3 6 10 15 4 4 6 10 15 3 222 Sample Output 0 1 3 3