You are given a set of n integers, and you want to take a subset of the integers, containing at least one integer, such that the multiplication of them forms a perfect square. An integer y is said to be a perfect square if y can be written as (x * x) where x is an integer. For example, 36 (6*6), 49 (7*7) etc are perfect squares.

For example, the given integers are 2, 3, 5, 10 and 6, then the resulting subsets are {2, 3, 6}, {2, 5, 10} and {3, 5, 6, 10}. For 4, 5 and 5 the resulting subsets are {4}, {5, 5} and {4, 5, 5}. For 4 and 4 the resulting subsets are {4}, {4} and {4, 4}.

Now your task is to find the number of ways to take the subsets such that the multiplication of a subset makes a perfect square.

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 1000). The next line contains n space separated integers denoting the set. You can assume that each of the integers lies in the range [2, 10¹⁵] and no integer contains a prime factor greater than 300.

For each case, print the case number and the total number of such subsets. Since the result can be very large, print the result modulo 1000000007 (10⁹ + 7).