Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Subset Multiplication

Limits: 1s, 512 MB

In mathematics, especially in set theory, a set A is a subset of a set B, or equivalently B is a superset of A if A is “contained” inside B, that is, all elements of A are also elements of B [source:https://en.wikipedia.org/wiki/Subset ].

You’re given a set of N positive integers. How many ways you can select two disjoint non-empty subsets, such that multiplication of elements in both subsets is equal.

Input

Input starts with an integer T (T ≤ 3), denoting the number of test cases. Each case contains an integer N (1 ≤ N ≤ 25) denoting the number of elements of an array. Next line contain array A of N distinct numbers, 1 ≤ A[i] ≤ 25.

Output

For each test case print the required answer on a line by itself.

Samples

InputOutput
2
1
1
6
1 2 3 4 5 6
0
6

Notes

For the second case, the valid combinations are:

[ 2, 3 ] and [ 6 ],

[ 1, 2, 3 ] and [ 6 ],

[ 2, 3 ] and [ 1, 6 ],

[ 3, 4 ] and [ 2, 6 ],

[ 1, 3, 4 ] and [ 2, 6 ] and

[ 3, 4 ] and [ 1, 2, 6 ]

Authors
Discussion
Submit

Login to submit