Cracking' RSA

Time Limit: 1 Second    Memory Limit: 32768 KB

The following problem is somehow related to the final stage of many famous integer factorization algorithms involved in some cryptoanalytical problems, for example cracking well-known RSA public key system.

The most powerful of such algorithms, so called quadratic sieve descendant algorithms utilize the fact that if n = pq where p and q are large unknown primes needed to be found out, then if v² = w² (mod n) and u != v (mod n) and u != -v (mod n) then gcd(v + w, n) is a factor of n (either p or q).

Not getting further in the details of these algorithms, let us consider our problem. Given m integer numbers b₁, b₂, ... , b^m such that all their prime factors are from the set of first t primes, the task is to find such a set S that S is a subset of {1, 2, ... ,m} and b₁*b₂*...*b_|S|(b_i belongs to S, i=1,2..|S|) is a perfect square i.e. equal to u₂ for some integer u. Given such S we get one pair for testing (product of S elements stands for v when w is known from other steps of algorithms which are of no interest to us, testing performed is checking whether pair is nontrivial, i.e. u != v (mod n) and u != -v (mod n)). Since we want to factor n with maximum possible probability, we would like to get as many such sets as possible. So the interesting problem could be to calculate the number of all such sets. This is exactly your task.

This problem contains multiple test cases!

The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.

Input

The first line of the input file contains two integers t and m (1 <= t <= 100, 1 <= m <= 100). The second line of the input file contains m integer numbers b_i such that all their prime factors are from t first primes (for example, if t = 3 all their prime factors are from the set {2, 3, 5}). 1 <= b_i <= 10⁹ for all i.

Output

Output the number of non-empty subsets of the given set b_i, the product of numbers from which is a perfect square.

Sample Input

1

3 4
9 20 500 3

Sample Output

3

Submit

Source: Andrew Stankevich's Contest #1