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.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
from sys import stdin
import functools
def gcd(a, b):  
 if (a == 0): 
  return b 
 return gcd(b % a, a) 
 
MAX=10001
def func(ind, g, dp, n, a): 
 if (ind == n):  
  if (g == 1):  
   return 1
  else: 
   return 0
 if (dp[ind][g] != -1):  
  return dp[ind][g] 
 ans = (func(ind + 1, g, dp, n, a) + 
   func(ind + 1, gcd(a[ind], g),  
        dp, n, a)) 
 dp[ind][g] = ans 
 return dp[ind][g] 
 
def countSubsequences(a, n):  
 dp = [[-1 for i in range(MAX)] 
    for i in range(n)] 
 count = 0
 for i in range(n):  
  count += func(i + 1, a[i], dp, n, a) 
 return count 

test=int(stdin.readline())
for _ in range(test):
 n=int(stdin.readline())
 list1=list(map(int,stdin.readline().split()))
 print(countSubsequences(list1,n))



from sys import stdin
import functools
def gcd(a, b):  
 if (a == 0): 
  return b 
 return gcd(b % a, a) 
 
# Recursive function to calculate the  
# number of subsequences with gcd 1  
# starting with particular index  
MAX=10001
def func(ind, g, dp, n, a): 
 
 # Base case  
 if (ind == n):  
  if (g == 1):  
   return 1
  else: 
   return 0
 
 # If already visited  
 if (dp[ind][g] != -1):  
  return dp[ind][g] 
 
 # Either we take or we do not  
 ans = (func(ind + 1, g, dp, n, a) + 
   func(ind + 1, gcd(a[ind], g),  
        dp, n, a)) 
 
 # Return the answer  
 dp[ind][g] = ans 
 return dp[ind][g] 
 
# Function to return the number  
# of subsequences  
def countSubsequences(a, n):  
 
 # Hash table to memoize  
 dp = [[-1 for i in range(MAX)] 
    for i in range(n)] 
 
 # Count the number of subsequences  
 count = 0
 
 # Count for every subsequence  
 for i in range(n):  
  count += func(i + 1, a[i], dp, n, a) 
 
 return count 
tc=int(stdin.readline())
for i in range(tc):
 n=int(stdin.readline())
 list1=list(map(int,stdin.readline().split()))
 print(countSubsequences(list1,n))



# cook your dish here
from math import gcd 

t = int(input())
for _t in range(t):
 n = int(input())
 arr = [int(x) for x in input().split()]
 dp = [[0]*10001 for i in range(n)]
 dp[0][arr[0]], sett = 1, set([arr[0]])
 for i in range(1, n):
  dp[i][arr[i]]+=1
  tmp = []
  for j in sett:
   dp[i][j] += dp[i-1][j]
   dp[i][gcd(j, arr[i])] += dp[i-1][j]
   tmp.append(gcd(j, arr[i]))
  sett.update(tmp)
  sett.add(arr[i])
 print(dp[n-1][1])

from math import gcd
from functools import reduce
# aa = []
def func(W,i,g,dp):
 # print(i,g)
 # aa.append(1)
 if i>=len(W):
  return 0
 if dp[i][g]!=-1:
  return dp[i][g]
 _g = gcd(g,W[i])
 ans1 = 1+func(W,i+1,_g,dp) if _g==1 else func(W,i+1,_g,dp)
 dp[i][g]= ans1+func(W,i+1,g,dp)
 return dp[i][g]
 # return ans1 + func(W,i+1,g,dp)
result = ""
for _ in range(int(input())) :
 n = int(input())
 W = [int(x) for x in input().split()]
 dp = [[-1 for x in range(10000+3)] for y in range(70)]
 
 # aa=[]
 
 t = func(W,0,0,dp) 
 # print(t,len(aa))
 result += str(t)+"\n"
print(result[:-1])
# submitted 03:05


def cal(a,b):
 if b==0:
  return a
 return cal(b,a%b)

def func(pos,cur_gcd):
 if pos==n:
  if cur_gcd==1:
   return 1
  else:
   return 0
 if (pos,cur_gcd) in dp:
  return dp[(pos,cur_gcd)]
 if cur_gcd==1:
  ans=2**(n-pos)
  dp[(pos,cur_gcd)]=ans
  return ans
 ans = func(pos+1,cal(cur_gcd,a[pos])) + func(pos+1,cur_gcd)
 dp[(pos,cur_gcd)]=ans
 return ans

for _ in range(int(input())):
 n = int(input())
 a = list(map(int,input().split()))
 dp = dict()
 ans = 0
 for i,j in enumerate(a):
  ans+=func(i+1,j)
 print(ans)

from math import gcd
def game(cPose,cGCD):
 if cPose==n:
  return 1 if cGCD==1 else 0

 if (cPose,cGCD) in dp:
  return dp[(cPose,cGCD)]
 
 dp[(cPose,cGCD)] = game(cPose+1,cGCD)+game(cPose+1,gcd(cGCD,l[cPose]))
 return dp[(cPose,cGCD)]
 
for _ in range(int(input())):
 n = int(input())
 l = list(map(int,input().split()))
 dp = {}; ans = 0
 for i in range(n):
  ans += game(i+1,l[i])
 print(ans)

from math import gcd
def game(cPose,cGCD):
 if cPose==n:
  return 1 if cGCD==1 else 0
 
 if cGCD==1:
  return 2**(n-cPose)
 
 if (cPose,cGCD) in dp:
  return dp[(cPose,cGCD)]
 
 dp[(cPose,cGCD)] = game(cPose+1,cGCD)+game(cPose+1,gcd(cGCD,l[cPose]))
 return dp[(cPose,cGCD)]
 
for _ in range(int(input())):
 n = int(input())
 l = list(map(int,input().split()))
 dp = {}; ans = 0
 for i in range(n):
  ans += game(i+1,l[i])
 print(ans)

def GCD(a,b):
 return a if b==0 else GCD(b,a%b)

def game(cPose,cGCD):
 if cPose==n:
  return 1 if cGCD==1 else 0
 
 if (cPose,cGCD) in dp:
  return dp[(cPose,cGCD)]
 
 dp[(cPose,cGCD)] = game(cPose+1,cGCD)+game(cPose+1,GCD(cGCD,l[cPose]))
 return dp[(cPose,cGCD)]
 
for _ in range(int(input())):
 n = int(input())
 l = list(map(int,input().split()))
 dp = {}; ans = 0
 for i in range(n):
  ans += game(i+1,l[i])
 print(ans)

def GCD(a,b):
 return a if b==0 else GCD(b,a%b)

def game(cPose,cGCD):
 if cPose==n:
  return 1 if cGCD==1 else 0
 
 if cGCD==1:
  return 2**(n-cPose)
 
 if (cPose,cGCD) in dp:
  return dp[(cPose,cGCD)]
 
 dp[(cPose,cGCD)] = game(cPose+1,cGCD)+game(cPose+1,GCD(cGCD,l[cPose]))
 return dp[(cPose,cGCD)]
 
for _ in range(int(input())):
 n = int(input())
 l = list(map(int,input().split()))
 dp = {}; ans = 0
 for i in range(n):
  ans += game(i+1,l[i])
 print(ans)

def gcd(a,b):
 if a == 0 or b == 0:
  if a == 0:
   return b
  else:
   return a
 else:
  return gcd(b,a%b)

def thegame(pos,cgcd):
 if pos == n:
  if cgcd == 1:
   return 1
  else:
   return 0
 elif (pos,cgcd) in dp:
  return dp[(pos,cgcd)]
 elif cgcd == 1:
  p = 2**(n-pos)
  dp[(pos,cgcd)] = p
  return p
 else:
  p = thegame(pos+1,gcd(cgcd,nums[pos])) + thegame(pos+1,cgcd)
  dp[(pos,cgcd)] = p
  return p

t = int(input())

while t>0:
 n = int(input())
 nums = list(map(int , input().split()))
 dp = {}
 res = 0
 for pos in range(0,n-1):
  res+=thegame(pos+1,nums[pos])
 print(res)
 t-=1


def func(ind, g, dp, n, a): 
 
 # Base case  
 if (ind == n):  
  if (g == 1):  
   return 1
  else: 
   return 0
 
 # If already visited  
 if (dp[ind][g] != -1):  
  return dp[ind][g] 
 
 # Either we take or we do not  
 ans = (func(ind + 1, g, dp, n, a) + 
   func(ind + 1, gcd(a[ind], g),  
        dp, n, a)) 
 
 # Return the answer  
 dp[ind][g] = ans 
 return dp[ind][g] 
 
 
def countSubsequences(a, n):  
 
 # Hash table to memoize  
 dp = [[-1 for i in range(MAX)] 
    for i in range(n)] 
 
 # Count the number of subsequences  
 count = 0
 
 # Count for every subsequence  
 for i in range(n):  
  count += func(i + 1, a[i], dp, n, a) 
 
 return count
t=int(input())
from math import gcd
for _ in range(t):
 n=int(input())
 l=list(map(int,input().split()))
 MAX=max(l)+1
 print(countSubsequences(l,n))


import math
MAX = 10001

def func(ind,g,n,dp,l):
 if ind==n:
  if g==1:
   return 1
  else:
   return 0
 
 if dp[ind][g]!=-1:
  return dp[ind][g]
 
 ans = func(ind+1,g,n,dp,l)+func(ind+1,math.gcd(g,l[ind]),n,dp,l)
 
 dp[ind][g]=ans
 return dp[ind][g]

for _ in range(int(input())):
 n = int(input())
 l = list(map(int,input().split()))
 dp = [[-1 for _ in range(MAX)]for _ in range(n)]
 
 count = 0
 for i in range(n):
  count+=func(i+1,l[i],n,dp,l)

  
 print(count)

# cook your dish here
for _ in range(int(input())):
 MAX = 10001
 def gcd(a, b):
  if (a == 0):
   return b
  return gcd(b % a, a)


 # Recursive function to calculate the
 # number of subsequences with gcd 1
 # starting with particular index
 def func(ind, g, dp, n, a):
  # Base case
  if (ind == n):
   if (g == 1):
    return 1
   else:
    return 0

  # If already visited
  if (dp[ind][g] != -1):
   return dp[ind][g]

   # Either we take or we do not
  ans = (func(ind + 1, g, dp, n, a) +
    func(ind + 1, gcd(a[ind], g),
     dp, n, a))

  # Return the answer
  dp[ind][g] = ans
  return dp[ind][g]


 # Function to return the number
 # of subsequences
 def countSubsequences(a, n):
  # Hash table to memoize
  dp = [[-1 for i in range(MAX)]
    for i in range(n)]

  # Count the number of subsequences
  count = 0

  # Count for every subsequence
  for i in range(n):
   count += func(i + 1, a[i], dp, n, a)
  return count


 # Driver Code
 N = int(input())
 a = [ int(x) for x in input().split()]
 print(countSubsequences(a, N))


from math import gcd

def f(cp,cg):
 nonlocal n,arr
 
 if cp == n and cg == 1:
  return 1
 elif cp == n:
  return 0
 elif cg == 1:
  return 2**(n-cp)
 elif (cp,cg) in d:
  return d[(cp,cg)]
 else:
  temp = f(cp+1,cg)+f(cp+1,gcd(arr[cp],cg))
  d[(cp,cg)] = temp
  return temp
 


t = int(input())

for _ in range(t):
 n = int(input())
 arr = list(map(int, input().split()))
 
 d = {}
 ans = 0
 for i in range(n):
  ans += f(i+1,arr[i])
 print(ans)

from math import gcd
def rec_ans(cp, cg):
 nonlocal n,nl
 if cp == n and cg == 1:
  return 1
 elif cp == n:
  return 0
 elif cg == 1:
  return 2**(n-cp)
 elif (cp,cg) in mem:
  return mem[(cp,cg)]
 else:
  temp = rec_ans(cp+1, gcd(cg,nl[cp])) + rec_ans(cp+1,cg)
  mem[(cp,cg)] = temp
  return temp
for _ in range(int(input())):
 n = int(input())
 nl = [int(x) for x in input().split()]
 mem = {}
 ans = 0
 for i in range(n):
  ans += rec_ans(i+1,nl[i])
 print(ans)

def gcd(a, b):
 return a if b == 0 else gcd(b, a % b)

def func(i, cur_gcd):
 if i == n:
  return 1 if cur_gcd == 1 else 0
 if cur_gcd == 1:
  return 2 ** (n - i)
 key = (i, cur_gcd)
 if key in d.keys():
  return d[key]
 d[key] = func(i+1, cur_gcd) + func(i+1, gcd(cur_gcd, ls[i]))
 return d[key]

for _ in range(int(input())):
 n, res = int(input()), 0
 ls = list(map(int, input().split()))
 d = {}
 for i in range(n):
  res += func(i+1, ls[i])
 print(res)

def gcd(a, b):
 return a if b == 0 else gcd(b, a % b)

def func(i, cur_gcd):
 if i == n:
  return 1 if cur_gcd == 1 else 0
 key = (i, cur_gcd)
 if key in d.keys():
  return d[key]
 d[key] = func(i+1, cur_gcd) + func(i+1, gcd(cur_gcd, ls[i]))
 return d[key]

for _ in range(int(input())):
 n, res = int(input()), 0
 ls = list(map(int, input().split()))
 d = {}
 for i in range(n):
  res += func(i+1, ls[i])
 print(res)

def gcd(a,b):
 if b == 0:
  return a
 return gcd(b,a%b)


t = int(input())
while t > 0:
 t = t-1
 n = int(input())
 L = list(map(int, input().split()))
 d = [1] + [0]*(10**4)
 for i in L:
  for j in range(1,(10**4)+1):
   if d[j]:
    d[gcd(min(i,j),max(i,j))] += d[j]
  d[i] += 1
 print(d[1])

import math
from _bisect import *
def factors(n):
 l = set()
 x = int(math.sqrt(n))
 for i in range(1,x+1):
  if n%i==0:
   l.add(i)
   if n//i!=i:
    l.add(n//i)
 return l
 
for T in range(int(input())):
 n = int(input())
 a = list(map(int,input().split()))
 divisors = set()
 for i in range(n):
  divisors = divisors.union(factors(a[i]))
 divisors = list(divisors)
 divisors.sort()
 oneIndex = -1
 for i in range(len(divisors)):
  if divisors[i] == 1:
   oneIndex = i
   break
 dp = [0 for x in range(len(divisors))]
 for i in range(n):
  for j in range(len(divisors)):
   x = 0
   if a[i] == divisors[j]:
    x = 1
   y = math.gcd(a[i],divisors[j])
   ind = bisect_left(divisors,y)
   dp[ind] += (x + dp[j])
 print(dp[oneIndex])

def gcd(a,b):
 if a == 0 or b == 0:
  if a == 0:
   return b
  else:
   return a
 else:
  return gcd(b,a%b)

def thegame(pos,cgcd):
 if pos == n:
  if cgcd == 1:
   return 1
  else:
   return 0
 elif (pos,cgcd) in dp:
  return dp[(pos,cgcd)]
 elif cgcd == 1:
  p = 2**(n-pos)
  dp[(pos,cgcd)] = p
  return p
 else:
  p = thegame(pos+1,gcd(cgcd,nums[pos])) + thegame(pos+1,cgcd)
  dp[(pos,cgcd)] = p
  return p

t = int(input())

while t>0:
 n = int(input())
 nums = list(map(int , input().split()))
 dp = {}
 res = 0
 for pos in range(0,n-1):
  res+=thegame(pos+1,nums[pos])
 print(res)
 t-=1