# 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

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

Input | Output |
---|---|

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 ]

Login to submit