"Everybody! Doremy's Perfect Math Class is about to start! Come and do your best if you want to have as much IQ as me!" In today's math class, Doremy is teaching everyone subtraction. Now she gives you a quiz to prove that you are paying attention in class.

You are given a set $S$ containing positive integers. You may perform the following operation some (possibly zero) number of times:

choose two integers $x$ and $y$ from the set $S$ such that $x > y$ and $x - y$ is not in the set $S$.

add $x-y$ into the set $S$.

You need to tell Doremy the maximum possible number of integers in $S$ if the operations are performed optimally. It can be proven that this number is finite.


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. The description of the test cases follows.

The first line contains an integer $n$ ($2 \le n\le 10^5$) — the size of the set $S$.

The second line contains $n$ integers $a_1,a_2,\dots,a_n$ ($1\le a_1 < a_2 < \cdots < a_n \le 10^9$) — the positive integers in $S$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.


-----Output-----

For each test case, you need to output the maximum possible number of integers in $S$. It can be proven that this value is finite.


-----Examples-----

Input
2
2
1 2
3
5 10 25
Output
2
5


-----Note-----

In the first test case, no such $x$ and $y$ exist. The maximum possible number of integers in $S$ is $2$.

In the second test case,

$S={5,10,25\}$ at first. You can choose $x=25$, $y=10$, then add $x-y=15$ to the set.

$S={5,10,15,25\}$ now. You can choose $x=25$, $y=5$, then add $x-y=20$ to the set.

$S={5,10,15,20,25\}$ now. You can not perform any operation now.

After performing all operations, the number of integers in $S$ is $5$. It can be proven that no other sequence of operations allows $S$ to contain more than $5$ integers.

Difficulty: EASY
Tags: Number theory

Mathematics

Starter code:

Solutions:
from math import gcd as gc
for i in [*open(0)][2::2]:
	l = list(map(int, i.split()))
	g = l[0]
	for j in l:
		g = gc(g, j)
	print(l[-1] // g)


import math
for s in [*open(0)][2::2]:
	d = 0
	for x in map(int, s.split()):
		d = math.gcd(d, x)
	print(x // d)


import sys
s = sys.stdin.read()
import math

def solve(data, lenght):
	data_list = map(int, data.split())
	d = 0
	for x in data_list:
		d = math.gcd(d, x)
	print(x // d)
lines = s.split('\n')
for index in range(1, len(lines) - 2, 2):
	lenght = int(lines[index])
	data = lines[index + 1]
	solve(data, lenght)


import sys
import math
FILE = False
if FILE:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def get_int():
	return int(sys.stdin.readline())

def get_string():
	return sys.stdin.readline().strip()

def write_int(n):
	return sys.stdout.write(str(n) + '\n')

def write_list(list):
	sys.stdout.write(' '.join(map(str, list)) + '\n')
test_cases = get_int()
for test in range(test_cases):
	n = get_int()
	input = [int(x) for x in get_string().split()]
	k = 0
	for n in input:
		k = math.gcd(k, n)
	result = input[-1] / k
	print(int(result))


import math
t = int(input())
l = []
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	m = max(a)
	hcf = a[0]
	for i in a:
		hcf = math.gcd(hcf, i)
	l.append(m // hcf)
for i in l:
	print(i)


import sys
import math

def solve():
	gcd = math.gcd
	inp = sys.stdin.readline
	n = int(inp())
	g = 0
	m = 0
	for v in map(int, inp().split()):
		g = gcd(g, v)
		m = max(m, v)
	print(m // g)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
t = inp()
for i in range(t):
	n = inp()
	l = li()
	s = set(l)
	m = sys.maxsize
	m2 = max(l)
	g = l[0]
	for i in range(n):
		g = gcd(g, l[i])
	print(m2 // g)


import math
import sys
input = lambda : sys.stdin.readline().strip()
x = int(input())
for i in range(x):
	y = int(input())
	k = list(map(int, input().split()))
	a = k[0]
	b = k[1]
	d = math.gcd(a, b)
	for i in range(2, y):
		d = math.gcd(d, k[i])
	print(max(k) // d)


import math
import sys
input = lambda : sys.stdin.readline().strip()
for i in range(int(input())):
	c = int(input())
	m = list(map(int, input().split()))
	gcdi = math.gcd(m[0], m[1])
	for i in range(2, c):
		gcdi = math.gcd(m[i], gcdi)
	print(m[-1] // gcdi)


import sys
from bisect import bisect_left, bisect_right
from heapq import heapify, heappush, heappop
from collections import deque
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
from collections import deque, defaultdict
input = sys.stdin.readline

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())
mod = 1000000000 + 7
dx = [-1, -2, 1, 2, 2, -2, -1, 1]
dy = [2, 1, 2, 1, -1, -1, -2, -2]
for _ in range(ii()):
	n = ii()
	arr = il()
	val = gcd(arr[0], arr[1])
	for i in range(1, n):
		val = gcd(val, arr[i])
	print(max(arr) // val)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	t = a[0]
	for x in a[1:]:
		t = gcd(t, x)
	print(max(a) // t)


from math import gcd
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	g = l[0]
	for i in l:
		g = gcd(i, g)
	print(max(l) // g)


from math import gcd
from functools import reduce
for (n, s) in ((int(input()), input()) for _ in range(int(input()))):
	arr = list(map(int, s.split(' ')))
	print(max(arr) // reduce(gcd, arr))


import math
t = int(input())

def solve():
	n = int(input())
	lst = list(map(int, input().split()))
	s = set()
	if lst[0] == 1:
		print(max(lst))
	else:
		ans = lst[0]
		for i in range(1, n):
			ans = math.gcd(ans, lst[i])
		if ans == 1:
			print(max(lst))
		else:
			print(lst[n - 1] // ans)
while t:
	solve()
	t -= 1


from math import gcd
from functools import reduce
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	fl = True
	a1 = reduce(gcd, a)
	if a1 != 1:
		print(a[n - 1] // a1)
	else:
		print(a[n - 1])


from math import gcd
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	g = 0
	for i in A:
		g = gcd(g, i)
	print(A[N - 1] // g)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	g = 0
	for i in range(n):
		g = gcd(g, a[i])
	print(a[-1] // g)


import sys
import math
input = lambda : sys.stdin.readline().strip()

def find_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
for i in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	c = []
	num1 = b[0]
	num2 = b[1]
	gcd = find_gcd(num1, num2)
	for i in range(2, len(b)):
		gcd = find_gcd(gcd, b[i])
	print(max(b) // gcd)


import os, sys, io, math
from array import *
from math import *
from bisect import *
from heapq import *
from functools import *
from itertools import *
from collections import *
I = lambda : [*map(int, sys.stdin.readline().split())]
IS = lambda : input()
IN = lambda : int(input())
IF = lambda : float(input())
for _ in range(IN()):
	(n, l, g) = (IN(), I(), 0)
	for i in l:
		g = gcd(g, i)
	print(l[-1] // g + (l[0] == 0))


from math import gcd
for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	g = arr[0]
	for j in arr:
		g = gcd(g, j)
	print(arr[-1] // g)


import math
from functools import reduce

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	i = reduce(math.gcd, a)
	m = max(a)
	print(m // i)
t = int(input())
for _ in range(t):
	solve()


import sys
t = int(sys.stdin.readline())

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
for i in range(t):
	n = int(sys.stdin.readline())
	arr = list(map(int, sys.stdin.readline().split()))
	g = 0
	for j in range(n):
		g = gcd(arr[j], g)
		if g == 1:
			break
	x = int(arr[-1] / g)
	sys.stdout.write(str(x) + '\n')


from math import gcd
MOD = int(100000.0 + 1)
for _ in range(int(input())):
	n = int(input()) % MOD
	arr = sorted(map(int, input().split()))
	common = 0
	for i in arr:
		common = gcd(common, i)
	print(arr[-1] // common)


t = int(input())
import math
for i in range(t):
	n = int(input())
	ans = 0
	array = list(map(int, input().split(' ')))
	for i in range(len(array)):
		ans = math.gcd(ans, array[i])
	print(int(array[len(array) - 1] / ans))


from math import gcd
from functools import reduce

def find_gcd(list):
	x = reduce(gcd, list)
	return x
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	gcf = find_gcd(a)
	print(max(a) // gcf)


import math
t = int(input())
for i in range(t):
	n = int(input())
	(*a,) = map(int, input().split())
	k = a[0]
	for j in a:
		k = math.gcd(j, k)
	print(a[-1] // k)


import math
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = 0
	for j in l:
		d = math.gcd(d, j)
	print(j // d)


import math

def gcd(list1):
	hcf = list1[0]
	for j in range(1, len(list1)):
		a = math.gcd(hcf, list1[j])
		hcf = a
	return hcf
t = int(input())
for i in range(0, t):
	n = int(input())
	l1 = input()
	S = list(map(int, l1.split()))
	ans = max(S) // gcd(S)
	print(ans)


import math
for _ in range(int(input())):
	input()
	l = list(map(int, input().split()))
	a = l[0]
	for i in l:
		a = math.gcd(a, i)
	print(max(l) // a)


from math import gcd

def solve():
	n = int(input())
	arr = [int(x) for x in input().split()]
	arr.sort()
	mx = arr[n - 1]
	ggcd = arr[0]
	for i in range(1, n):
		ggcd = gcd(arr[i], ggcd)
	if ggcd == 1:
		print(mx)
	else:
		mn = ggcd
		count = (mx - mn) // ggcd + 1
		print(count)
t = int(input())
for i in range(t):
	solve()


import math
from collections import *

def solve():
	n = int(input())
	a = [int(i) for i in input().split()]
	g = 0
	for i in a:
		g = math.gcd(g, i)
	print(a[n - 1] // g)
t = int(input())
for _ in range(t):
	solve()


from math import gcd
for i in range(int(input())):
	k = int(input())
	d = list(map(int, input().split()))
	g = max(d)
	f = d[0]
	for i in range(1, k):
		f = gcd(f, d[i])
	print(g // f)


import math
for t in range(0, int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = a[0]
	for i in range(1, n):
		x = math.gcd(x, a[i])
	print(int(a[n - 1] / x))


from math import gcd
t = int(input())
for i in range(t):
	n = int(input())
	l1 = list(map(int, input().split()))
	l = sorted(l1)
	mx = max(l)
	le = len(l)
	g = l[0]
	for j in l[1:]:
		g = gcd(g, j)
	print(mx // g)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	gcd = arr[0]
	for num in arr[1:]:
		gcd = math.gcd(gcd, num)
	print(max(arr) // gcd)


from math import *
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	x = max(l)
	y = l[0]
	for i in range(1, n):
		y = gcd(y, l[i])
	print(x // y)


from math import *

def solve(n, l):
	gcd_a = l[0]
	for i in range(1, n):
		gcd_a = gcd(gcd_a, l[i])
	return l[-1] // gcd_a
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(solve(n, l))


import math
t = int(input())
for _ in range(t):
	n = int(input())
	S = list(map(int, input().split()))
	k = S[0]
	for i in S:
		k = math.gcd(k, i)
	print(S[-1] // k)


from math import gcd as gcd
for _ in range(int(input())):
	x = int(input())
	l = list(map(int, input().split()))
	g = l[0]
	for i in range(1, x):
		g = gcd(g, l[i])
	print(max(l) // g)


import math

def res(n, a):
	ans = a[0]
	for x in a:
		ans = math.gcd(x, ans)
	ans = max(a) // ans
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	print(res(n, a))


import math
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	maxa = max(a)
	w = 0
	for x in a:
		w = math.gcd(w, x)
	print(maxa // w)


from math import gcd

def solve(nums):
	if len(nums) == 1:
		return nums[0]
	div = gcd(nums[0], nums[1])
	if len(nums) == 2:
		return div
	for i in range(1, len(nums) - 1):
		div = gcd(div, nums[i + 1])
		if div == 1:
			return div
	return div
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().strip().split()]
	v = solve(a)
	print(a[-1] // v)


def gcd(a, b):
	r = 0
	while b > 0:
		r = a % b
		a = b
		b = r
	return a
for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split(' ')]
	gcd_all = arr[0]
	for i in arr:
		gcd_all = gcd(gcd_all, i)
	print(arr[-1] // gcd_all)


from math import gcd
I = lambda : int(input())
Is = lambda : map(int, input().split())
Li = lambda : list(map(int, input().split()))

def solve():
	n = I()
	lst = Li()
	lst.sort(reverse=True)
	s = lst[0]
	for i in range(1, n):
		s = gcd(s, lst[i])
	print(lst[0] // s)
	return 1
t = I()
while t:
	solve()
	t -= 1


from math import gcd
for jj in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	t = arr[0]
	for i in range(1, n):
		t = gcd(t, arr[i])
	print(max(arr) // t)


from math import gcd
from functools import reduce

def find_gcd(lst):
	x = reduce(gcd, lst)
	return x
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = find_gcd(a)
	M = a[n - 1]
	answer = M // d
	print(answer)


import math
from collections import Counter

def li():
	return list(map(int, input().split()))

def n():
	return int(input())

def st():
	return input()
yes = 'YES'
no = 'NO'
even = 'EVEN'
odd = 'ODD'

def prefix(L):
	size = len(L)
	for i in range(1, size):
		L[i] = L[i] + L[i - 1]
	return L
for _ in range(int(input())):
	x = n()
	L = li()
	g = 0
	for i in L:
		g = math.gcd(g, i)
	print(L[-1] // g)


import math
k = int(input())
for q in range(k):
	n = int(input())
	a = list(map(int, input().split()))
	flag = 0
	temp = a[0]
	for i in range(1, n):
		temp = math.gcd(temp, a[i])
		if temp == 0:
			flag = 1
			break
	if flag == 1:
		print(a[-1])
	else:
		print(int(a[-1] / temp))


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	mm = a[0]
	for i in range(1, len(a)):
		mm = math.gcd(mm, a[i])
		if mm == 1:
			break
	print(a[n - 1] // mm)


import math
t = int(input())
while t != 0:
	n = int(input())
	g = mx = 0
	arr = list(map(int, input().split()))
	for i in range(n):
		g = math.gcd(g, arr[i])
	mx = arr[n - 1] // g
	print(mx)
	t -= 1


import math
for tcas in range(int(input())):
	n = int(input())
	list1 = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		ans = math.gcd(ans, list1[i])
	print(list1[n - 1] // ans)


def func(lst):
	g = lst[0]
	for elem in lst:
		g = gcd(elem, g)
	return max(lst) // g

def gcd(a, b):
	while b != 0:
		(b, a) = (a % b, b)
	return a
t = int(input())
for i in range(t):
	int(input())
	print(func(list(map(int, input().split()))))


import math

def fun(st):
	gc = math.gcd(st[0], st[1])
	for i in range(2, len(st)):
		gc = math.gcd(gc, st[i])
		if gc == 1:
			break
	if gc == 1:
		print(st[len(st) - 1])
	else:
		v = (st[len(st) - 1] - gc) / gc
		print(int(v) + 1)

def parsing():
	k = int(input())
	while k > 0:
		n = int(input())
		st = input()
		st = list(map(int, st.split(' ')))
		fun(st)
		k -= 1
parsing()


import math
t = int(int(input()))
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	m = max(arr)
	f = arr[0]
	for v in range(1, len(arr)):
		f = math.gcd(f, arr[v])
	if f != 1:
		print(m // f)
	else:
		print(m)


def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	fac = gcd(a[0], a[1])
	for i in range(2, n):
		fac = gcd(fac, a[i])
	print(a[n - 1] // fac)


import math
t = int(input())
for _ in range(t):
	gcd1 = 0
	n = int(input())
	m = list(map(int, input().split()))
	for i in range(0, len(m)):
		gcd1 = math.gcd(gcd1, m[i])
	print(max(m) // gcd1)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	m = max(a)
	r = a[0]
	for i in range(1, n):
		r = math.gcd(r, a[i])
	print(m // r)


TT = int(input())
import functools
import math
from math import gcd
while TT:
	n = int(input())
	a = list(map(int, input().split(' ')))
	a.sort()
	now = a[0]
	for i in range(1, n):
		now = gcd(now, a[i])
	if now == 1:
		print(max(a))
	else:
		print(max(a) // now)
	TT -= 1


from sys import setrecursionlimit
from bisect import bisect_left
from bisect import bisect_right
from getopt import getopt
from re import sub
import re
from os import path
import random
from math import gcd
from typing import DefaultDict
import math
from collections import defaultdict
from math import sqrt
import collections
from sys import maxsize
from itertools import combinations_with_replacement
import sys
import copy
import heapq
from collections import Counter
from collections import deque
mod1 = 998244353
mod = 10 ** 9 + 7
sys.setrecursionlimit(10 ** 7)
vowels = 'aeiou'
MAX = float('inf')
MIN = float('-inf')
if path.exists('INPUT.txt'):
	sys.stdin = open('INPUT.txt', 'r')
	sys.stdout = open('OUTPUT.txt', 'w')
for _ in range(int(input())):
	s = int(input())
	lst = list(map(int, input().split()))
	maxi = max(lst)
	if s < 2:
		print(s)
	else:
		x = lst[0]
		y = lst[1]
		ans = math.gcd(x, y)
		for i in range(2, s):
			ans = math.gcd(ans, lst[i])
		print(maxi // ans)


import math
for _ in range(int(input())):
	n = int(input())
	num = list(map(int, input().split()))
	a = num[0]
	for i in range(n):
		a = math.gcd(a, num[i])
	if a == 1:
		print(num[-1])
	else:
		print(num[-1] // a)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	if a[0] == 1:
		print(a[n - 1])
		continue
	g = math.gcd(a[0], a[1])
	for i in range(1, n):
		g = math.gcd(g, a[i])
	print(a[-1] // g)


def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = a[0]
	for i in range(n):
		x = gcd(x, a[i])
	a.sort()
	ans = a[-1] // x
	print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if n == 1:
		print(1)
		continue
	gcdnum = math.gcd(arr[0], arr[1])
	for num in arr[2:]:
		gcdnum = math.gcd(gcdnum, num)
	alldiv = True
	isOneOdd = False
	for num in arr:
		if num % gcdnum != 0:
			alldiv = False
		if num & 1:
			isOneOdd = True
	if alldiv:
		print(max(arr) // gcdnum)
	elif isOneOdd:
		print(max(arr))
	else:
		print(max(arr) // 2)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	k = max(a)
	temp = a[0]
	for i in range(n):
		temp = math.gcd(temp, a[i])
	print(k // temp)


import math
T = int(input())
for tc in range(T):
	n = int(input())
	a = 0
	l1 = list(map(int, input().split()))
	for i in range(n):
		a = math.gcd(a, l1[i])
	print(max(l1) // a)


from math import gcd
from functools import reduce
for _ in range(0, int(input())):
	n = input()
	a = sorted([int(i) for i in input().split()])
	if len(a) > 1:
		s = a[0]
		for i in a[1:]:
			s = gcd(s, i)
			if s == 1:
				break
		print(a[-1] // s)
	else:
		print(1)


from math import gcd
for t in range(int(input())):
	n = int(input())
	l_list = list(map(int, input().split()))
	l_list.sort()
	gcd_result = 0
	for x in range(n):
		gcd_result = gcd(gcd_result, l_list[x])
	print(max(l_list) // gcd_result)