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.

Source: codechef | Difficulty: HARD
Tags: Number theory

Dynamic programming

Mathematics


Solutions:
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)


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)


for _ in range(int(input())):
	MAX = 10001

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

	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
	N = int(input())
	a = [int(x) for x in input().split()]
	print(countSubsequences(a, N))


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])


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:
		return b
	return gcd(b % a, a)

def solve(idx, g):
	if idx < 0:
		return 1 if g == 1 else 0
	if dp[idx][g] != -1:
		return dp[idx][g]
	dp[idx][g] = solve(idx - 1, g) + solve(idx - 1, gcd(g, arr[idx]))
	return dp[idx][g]
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	dp = [[-1 for j in range(10001)] for i in range(n)]
	ans = solve(n - 1, 0)
	print(ans)


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))


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])


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)


from math import gcd
from functools import reduce

def func(W, i, g, dp):
	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]
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)]
	t = func(W, 0, 0, dp)
	result += str(t) + '\n'
print(result[:-1])


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 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
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))


from collections import defaultdict

def makeLPF(f_limit):
	lpf = [2, 1] * (f_limit // 2 + 1)
	lpf[0:3] = [0, 0, 1]
	k = 3
	while k * k <= f_limit:
		if lpf[k] == 1:
			for m in range(k * k, f_limit + 1, 2 * k):
				if lpf[m] == 1:
					lpf[m] = k
		k += 2
	return lpf

def pFac(val, lpf):
	facs = set()
	afac = lpf[val]
	while afac > 1:
		facs.add(afac)
		val //= afac
		afac = lpf[val]
	if afac == 1:
		facs.add(val)
	return tuple(sorted(facs))

def coprime_paths(faclist):
	spread = defaultdict(int)
	for facs in faclist:
		for (skey, sct) in list(spread.items()):
			comb = tuple((f for f in facs if f in skey))
			spread[comb] += sct
		spread[facs] += 1
	return spread[tuple()]
lim = 10000
lpf = makeLPF(lim)
T = int(input())
for tx in range(T):
	N = int(input())
	vals = sorted((pFac(int(a), lpf) for a in input().split()))
	print(coprime_paths(vals))


from collections import defaultdict

def makeFTable(f_limit):
	fTable = [[] for ix in range(f_limit + 1)]
	for ix in range(2, f_limit + 1, 2):
		fTable[ix] = [2]
	k = 3
	while k <= f_limit:
		if not fTable[k]:
			for m in range(k, f_limit + 1, k):
				fTable[m].append(k)
		k += 2
	return fTable

def coprime_paths(faclist):
	spread = defaultdict(int)
	for facs in faclist:
		for (skey, sct) in list(spread.items()):
			comb = tuple((f for f in facs if f in skey))
			spread[comb] += sct
		spread[facs] += 1
	return spread[tuple()]
lim = 10000
fTable = makeFTable(lim)
T = int(input())
for tx in range(T):
	N = int(input())
	vals = list((tuple(fTable[int(a)]) for a in input().split()))
	print(coprime_paths(vals))


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


t = int(input())

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

def SubSequences(i, con, a, sol):
	if i < 0:
		if con == 1:
			return 1
		else:
			return 0
	if (i, con) in sol:
		return sol[i, con]
	sol[i, con] = SubSequences(i - 1, gcd(a[i], con), a, sol) + SubSequences(i - 1, con, a, sol)
	return sol[i, con]
while t > 0:
	t -= 1
	n = int(input())
	a = [int(x) for x in input().split()]
	print(SubSequences(n - 1, 0, a, {}))


from sys import stdin

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

def solve(dp, index, g, arr, n):
	if index in dp and g in dp[index]:
		return dp[index][g]
	if index == n and g != 1:
		dp[index][g] = 0
		return dp[index][g]
	dp[index][g] = solve(dp, index + 1, g, arr, n) + solve(dp, index + 1, gcd(g, arr[index]), arr, n)
	return dp[index][g]
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	cnt = 0
	dp = {}
	for i in range(n + 1):
		dp[i] = {}
	dp[n][1] = 1
	print(solve(dp, 0, 0, arr, n))


from math import gcd
from collections import defaultdict
for _ in range(int(input())):
	num_elements = int(input())
	num_list = list(map(int, input().split()))
	mem = [defaultdict(int) for i in range(num_elements)]
	mem[0][num_list[0]] = 1
	for num_i in range(1, num_elements):
		mem[num_i][num_list[num_i]] += 1
		for prev_num_i in range(num_i):
			for divisor in mem[prev_num_i]:
				mem[num_i][gcd(num_list[num_i], divisor)] += mem[prev_num_i][divisor]
	required_sub_seq_count = 0
	for num_i in range(num_elements):
		required_sub_seq_count += mem[num_i][1]
	print(required_sub_seq_count)


from math import gcd
cases = int(input())
for _ in range(cases):
	n = int(input())
	arr = list(map(int, input().split()))
	cache = {}

	def compute(pos, curgcd):
		if pos == n:
			return int(curgcd == 1)
		if curgcd == 1:
			return 2 ** (n - pos)
		if (pos, curgcd) in cache:
			return cache[pos, curgcd]
		val = compute(pos + 1, curgcd) + compute(pos + 1, gcd(curgcd, arr[pos]))
		cache[pos, curgcd] = val
		return val
	print(sum([compute(i + 1, arr[i]) for i in range(n)]))


from sys import stdin
read = stdin.readline
dp = {}
T = int(read())
N = 0
arr = []
ans = 0
gcd = lambda a, b: a if not b else gcd(b, a % b)

def fn(i, g):
	if i == N:
		if g == 1:
			return 1
		else:
			return 0
	elif g == 1:
		return 1 << N - i
	elif (i, g) in dp:
		return dp[i, g]
	else:
		dp[i, g] = fn(i + 1, gcd(arr[i], g)) + fn(i + 1, g)
		return dp[i, g]
for _ in range(T):
	N = int(read())
	arr = list(map(int, read().split()))
	dp = {}
	ans = 0
	for i in range(0, N - 1):
		ans = ans + fn(i + 1, arr[i])
	print(ans)


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)


import sys
sys.setrecursionlimit(10 ** 9)

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

def solve(dp, index, g, arr, N):
	if index in dp and g in dp[index]:
		return dp[index][g]
	if index == N and g != 1:
		dp[index][g] = 0
		return dp[index][g]
	dp[index][g] = solve(dp, index + 1, g, arr, N) + solve(dp, index + 1, gcd(g, arr[index]), arr, N)
	return dp[index][g]
for _ in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	dp = {}
	for i in range(N + 1):
		dp[i] = {}
	dp[N][1] = 1
	print(solve(dp, 0, 0, arr, 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)