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

By khatribiru, Bhadra, Bishal_G, mihassan · Limits 1s, 512 MB

In mathematics, especially in set theory, set A is a subset of set B, or equivalently B is a superset of set A if A is contained inside B, that is, all elements of A are also elements of B.

You’re given a set of N positive integers. How many ways can you select two disjoint non-empty subsets, such that the 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. The next line contain array A (1 ≤ A[i] ≤ 25) of N distinct numbers.

Output

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

Sample

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

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}
  • {3, 4} and {1, 2, 6}

Discussion

Statistics


84% Solution Ratio

IOI_StfuFfsEarliest, May '18

sarwarITFastest, 0.3s

flash_7Lightest, 131 kB

sarwarITShortest, 1096B

Submit

Login to submit