Chef is playing a game on a sequence of $N$ positive integers, say $A_1, A_2, ... A_N$ The game is played as follows.
- If all the numbers are equal, the game ends.
- Otherwise
- Select two numbers which are unequal
- Subtract the smaller number from the larger number
- Replace the larger number with the result from above
Chef has already figured out that the game always terminates. He also knows, for a given sequence of integers, the game will always terminate on the same value, no matter how the game is played. Chef wants you to simulate the game for him and tell him if the game terminates on $1$.
In fact, there may be many such games. Given a sequence of integers Chef wants to know the number of sub-sequences of the given sequence, for which, playing the above game on the subsuquence will terminate on $1$. A sub-sequence can be obtained from the original sequence by deleting $0$ or more integers from the original sequence. See the explanation section for clarity.

-----Input-----
- The first line of the input contains an integer $T$, the number of test cases. Then follow the description of $T$ test cases. 
- The first line of each test case contains a single integer $N$, the length of the sequence. 
- The second line contains $N$ positive integers, each separated by a single space.

-----Output-----
For each test case, output a single integer - the number of sub-sequences of the original sequence, such that, playing the game on the sub-sequence results in ending the game with all the values equal to $1$.

-----Constraints-----
- $1 \le T \le 100$ 
- $1 \le N \le 60$ 
- $1 \le A_i \le 10^4$ 
- All $A_i$ will be distinct.

-----Sample Input-----
3
4
2 3 5 7
4
3 4 8 16
3
6 10 15

-----Sample Output-----
11
7
1

-----Explanation-----
Test Case 1: The following $11$ sub-sequences are counted.
- $\{ 2, 3 \}$
- $\{ 2, 5 \}$
- $\{ 2, 7 \}$
- $\{ 3, 5 \}$
- $\{ 3, 7 \}$
- $\{ 5, 7 \}$
- $\{ 2, 3, 5 \}$
- $\{ 2, 3, 7 \}$
- $\{ 2, 5, 7 \}$
- $\{ 3, 5, 7 \}$
- $\{ 2, 3, 5, 7 \}$
Test Case 2: The following $7$ sub-sequences are counted.
- $\{ 3, 4 \}$
- $\{ 3, 8 \}$
- $\{ 3, 16 \}$
- $\{ 3, 4, 8 \}$
- $\{ 3, 4, 16 \}$
- $\{ 3, 8, 16 \}$
- $\{ 3, 4, 8, 16 \}$
Test Case 3: There are $8$ subsequences of $\{ 6, 10, 15 \}$
- $\{\}$ => The game cannot be played on this sub-sequence
- $\{ 6 \}$ => The game cannot be played on this sub-sequence
- $\{ 10 \}$ => The game cannot be played on this sub-sequence
- $\{ 15 \}$ => The game cannot be played on this sub-sequence
- $\{ 6, 10 \}$ => The game cannot end at $\{ 1, 1 \}$
- $\{ 6, 15 \}$ => The game cannot end at $\{ 1, 1 \}$
- $\{ 10, 15 \}$ => The game cannot end at $\{ 1, 1 \}$
- $\{ 6, 10, 15 \}$ => The game ends at $\{ 1, 1, 1 \}$. Hence this is the only sub-sequence that is counted in the result.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'from sys import stdin\nimport functools\ndef gcd(a, b):  \n if (a == 0): \n  return b \n return gcd(b % a, a) \n \n# Recursive function to calculate the  \n# number of subsequences with gcd 1  \n# starting with particular index  \nMAX=10001\ndef func(ind, g, dp, n, a): \n \n # Base case  \n if (ind == n):  \n  if (g == 1):  \n   return 1\n  else: \n   return 0\n \n # If already visited  \n if (dp[ind][g] != -1):  \n  return dp[ind][g] \n \n # Either we take or we do not  \n ans = (func(ind + 1, g, dp, n, a) + \n   func(ind + 1, gcd(a[ind], g),  \n        dp, n, a)) \n \n # Return the answer  \n dp[ind][g] = ans \n return dp[ind][g] \n \n# Function to return the number  \n# of subsequences  \ndef countSubsequences(a, n):  \n \n # Hash table to memoize  \n dp = [[-1 for i in range(MAX)] \n    for i in range(n)] \n \n # Count the number of subsequences  \n count = 0\n \n # Count for every subsequence  \n for i in range(n):  \n  count += func(i + 1, a[i], dp, n, a) \n \n return count \ntc=int(stdin.readline())\nfor i in range(tc):\n n=int(stdin.readline())\n list1=list(map(int,stdin.readline().split()))\n print(countSubsequences(list1,n))\n\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 348737