You are given an array $a$ consisting of $n$ integers.

Your task is to say the number of such positive integers $x$ such that $x$ divides each number from the array. In other words, you have to find the number of common divisors of all elements in the array.

For example, if the array $a$ will be $[2, 4, 6, 2, 10]$, then $1$ and $2$ divide each number from the array (so the answer for this test is $2$).


-----Input-----

The first line of the input contains one integer $n$ ($1 \le n \le 4 \cdot 10^5$) — the number of elements in $a$.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^{12}$), where $a_i$ is the $i$-th element of $a$.


-----Output-----

Print one integer — the number of such positive integers $x$ such that $x$ divides each number from the given array (in other words, the answer is the number of common divisors of all elements in the array).


-----Examples-----
Input
5
1 2 3 4 5

Output
1

Input
6
6 90 12 18 30 18

Output
4

Difficulty: introductory

Starter code:

Solutions:
from  math import gcd
n = int(input())
a=  list(map(int, input().split()))
k  = 0
for i in range(n):
    k = gcd(a[i], k)

ans = 0

def fact(n):
    nonlocal ans
    d = 1
    while d* d <= n:
        if n % d == 0:
            ans += 1
            if n // d != d:
                ans += 1
        d += 1
fact(k)
print(ans)

from math import gcd
from math import sqrt


def factor(n):
    potentional_p = 3
    itog_list = {}
    if n % 2 == 0:
        itog_list[2] = 0
    while n % 2 == 0:
        n = n // 2
        itog_list[2] += 1
    while n - 1:
        if potentional_p > sqrt(n):
            if n in itog_list:
                itog_list[n] += 1
            else:
                itog_list[n] = 1
            return itog_list
        while n % potentional_p == 0:
            n = n // potentional_p
            if potentional_p in itog_list:
                itog_list[potentional_p] += 1
            else:
                itog_list[potentional_p] = 1
        potentional_p += 2
    return itog_list


n = int(input())
A = list(map(int, input().split()))
g = 1
if n == 1:
    g = A[0]
else:
    g = gcd(A[0], A[1])
    for i in range(2, n):
        g = gcd(g, A[i])
F = factor(g)
ans = 1
for i in F:
    ans *= (F[i] + 1)
print(ans)

n = int(input())
A = [int(i) for i in input().split()]

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

g = A[0]

for i in A:
    g = gcd(g, i)

fct = []

for i in range(1, g+1):
    if i*i > g:
        break
    if g%i == 0:
        fct.append(i)
        fct.append(g//i)

print(len(set(fct)))


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

n = int(input())
a = [int(c) for c in input().split()]

g = a[0]
for i in range(1, n):
    g = gcd(g, a[i])

ans = 0
for i in range(1, int(g ** (0.5)) + 1):
    if g % i == 0:
        if g // i != i:
            ans += 2
        else:
            ans += 1

print(ans)


from math import gcd

n = int(input())
*l, = map(int, input().split())

tmp = l[0]
for i in range(1, n):
	tmp = gcd(tmp, l[i])

if tmp != 1:
	c = 2
	for i in range(2, int(tmp**.5+1)):
		if tmp % i == 0:
			c += 2
			if i * i == tmp:
				c -= 1
	print(c)
else:
	print(1)

import math


def fnl(n) : 
    c=0
    ln=(int)(math.sqrt(n))
    for i in range(1,ln+1) : 
        if (n%i==0) : 
            if(n/i==i) : 
                c+=1
            else:
                c+=2         
    return c 


N=int(input())
s=[int(x) for x in input().split()]
c=s[0]
for i in range(1,len(s)):
    c=math.gcd(c,s[i])

ans=fnl(c)
print(ans)





from math import gcd

# THis is the main function 
def main():
    n = int(input())
    a = [int(c) for c in input().split()]

    g = a[0]
    for i in range(1, n):
        g = gcd(g, a[i])

    final=0
    for i in range(1, int(g ** (0.5)) + 1):
        if g % i == 0:
            if g // i != i:
                final += 2
            else:
                final += 1

    print(final)

main()



import math

def divs(x):
    ans = 0
    d = 1
    while d*d <= x:
        if x%d == 0:
            ans += 2
            ans -= (d*d==x)
        d+= 1
    return ans

n = int(input())
arr = [int(x) for x in input().split()]

gcd = arr[0]
for a in arr:
    gcd = math.gcd(a,gcd)


print(divs(gcd))



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


n = int(input())
a = list(map(int, input().split()))
g = 0
for x in a:
    g = gcd(g, x)
ans = 0
t = 1
while t * t <= g:
    if g % t == 0:
        ans += 1
        if t * t != g:
            ans += 1
    t += 1
print(ans)

from sys import stdin, stdout

input = stdin.readline

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

def divisors(x):
    res = 0
    d = 1
    while d * d <= x:
        if x % d == 0:
            res += 1
            res += (d != x / d)
        d += 1

    return res

n = int(input())
a = [int(i) for i in input().split()]
nwd = 0
for i in a:
    nwd = gcd(nwd, i)

print(divisors(nwd))


import math
from functools import reduce

n = int(input())
a = list(map(int, input().split()))
x = reduce(math.gcd, a)

i = 1
cnt = 0
while i * i < x:
	if x % i == 0:
		cnt += 2
	i += 1
if i * i == x:
	cnt += 1
print(cnt)


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


def razl(n):
	cnt = 0
	i = 1
	while (i * i < n):
		if (n % i == 0):
			cnt += 2
		i += 1
	if (i * i == n):
		cnt += 1
	return cnt


n = int(input())
ans = 0
for i in map(int, input().split()):
	ans = gcd(ans, i)
print(razl(ans))

def gcd(n1,n2):
    if n2 > n1:
        return gcd(n2,n1)
    if n2 == 0:
        return n1
    return gcd(n2,n1%n2)

def factors(n):
    ans = 0
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ans += 1
            if i != n//i:
                ans += 1

    return ans

def main():
    n = int(input())
    arr = list(map(int,input().split()))
    g = 0
    for i in arr:
        g = gcd(i,g)
    
    facts = factors(g)
    print(facts)

main()


import math
# helpful:
# r,g,b=map(int,input().split())
#list1 = input().split()
#for i in range(len(list1)):
#    list1[i] = int(list1[i])
#print(list1)
# arr = [[0 for x in range(columns)] for y in range(rows)]

n = int(input())
list1 = input().split()
for i in range(len(list1)):
    list1[i] = int(list1[i])
gcd1 = list1[0]
for i in range(n):
    gcd1 = math.gcd(gcd1,list1[i])

val = 0

if(int(math.sqrt(gcd1))**2 == gcd1):
    val -= 1

for i in range(1, int(math.sqrt(gcd1))+ 1):
    if(gcd1 % i == 0):
        val += 2

print(val)
        


from functools import reduce

def gcd(a, b):
    while b: a, b = b, a % b
    return abs(a)
def gcd_mult(numbers):
    return reduce(gcd, numbers)
def primeFactor(N):
    i, n, ret, d, sq = 2, N, {}, 2, 99
    while i <= sq:
        k = 0
        while n % i == 0: n, k, ret[i] = n//i, k+1, k+1
        if k > 0 or i == 97: sq = int(n**(1/2)+0.5)
        if i < 4: i = i * 2 - 1
        else: i, d = i+d, d^6
    if n > 1: ret[n] = 1
    return ret
def divisors(N):
    pf = primeFactor(N)
    ret = [1]
    for p in pf:
        ret_prev = ret
        ret = []
        for i in range(pf[p]+1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return sorted(ret)

N = int(input())
A = [int(a) for a in input().split()]
G = gcd_mult(A)
print(len(divisors(G)))





import math
def countDivisors(n) : 
    cnt = 0
    for i in range(1, (int)(math.sqrt(n)) + 1) : 
        if (n % i == 0) : 
              
            # If divisors are equal, 
            # count only one 
            if (n / i == i) : 
                cnt = cnt + 1
            else : # Otherwise count both 
                cnt = cnt + 2
    return cnt 
x=int(input())
l=list(map(int,input().split()))
g=l[0]
for i in range(1,x):
       g=math.gcd(g,l[i])
print(countDivisors(g))
  
   #t-=1


from math import gcd

t = int(input())
a = list(map(int, input().split()))

n = a[0]

for c in a:
	n = gcd(n, c)


ans = 1
for i in range(2, int(n ** 0.5 + 0.5) + 1):
	if n % i == 0:
		kol = 0
		for x in range(100000000):
			if n % i == 0:
				kol += 1
				n //= i
			else:
				break
		ans *= (kol + 1)

if n > 1:
	ans *= 2

print(ans)



import io, sys, atexit, os
import math as ma
from decimal import Decimal as dec
from itertools import permutations
from itertools import combinations


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


def num ():
	return map (int, input ().split ())


def nu ():
	return int (input ())


def find_gcd ( x, y ):
	while (y):
		x, y = y, x % y
	return x


def lcm ( x, y ):
	gg = find_gcd (x, y)
	return (x * y // gg)


def printDivisors ( n ):
	# Note that this loop runs till square root
	i = 1
	cc=0
	while i <= ma.sqrt (n):

		if (n % i == 0):

			# If divisors are equal, print only one
			if (n / i == i):
				cc+=1
			else:
				# Otherwise print both
				cc+=2
		i = i + 1
	return cc

mm = 1000000007
yp = 0


def solve ():
	t = 1
	for tt in range (t):
		n=nu()
		a=li()
		gg=0
		for i in range(n):
			gg=find_gcd(gg,a[i])
		cc=0
		print(printDivisors(gg))




def __starting_point():
	solve ()
__starting_point()

#579_C

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

n = int(input())

ln = [int(i) for i in input().split(" ")]

m = ln[0]

for i in range(1, len(ln)):
    m = gcd(m, ln[i])

d = 0

for i in range(1, int(m ** 0.5) + 1):
    if m % i == 0:
        d += 2
        if i == m ** 0.5:
            d -= 1

print(d)


import math

def find_gcd(x, y): 
	
	while(y): 
		x, y = y, x % y 
	
	return x 
 
def calcDivisors(n) : 
	ans=0
	i = 1
	while i <= math.sqrt(n): 
		
		if (n % i == 0) : 
			 
			if (n / i == i) : 
				ans=ans+1
			else : 
				ans=ans+2 
		i = i + 1
	return ans	


			 
n=int(input())			 
l = [int(i) for i in input().split()] 

if n!=1:
	gcd = find_gcd(l[0], l[1])
if n==1:
	gcd=l[0] 

for i in range(2, n): 
	gcd = find_gcd(gcd, l[i]) 
	
print(calcDivisors(gcd)) 


  
def countDivisors(n) : 
	cnt = 0
	for i in range(1, int(n**(0.5)) + 1) : 
		if (n % i == 0) : 
			if (n / i == i) : 
				cnt = cnt + 1
			else : 
				cnt = cnt + 2
	return cnt 


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

n=int(input())
l=list(map(int,input().split()))
if n==1:
	print(countDivisors(l[0]))
else:
	hcf=gcd(l[0],l[1])
	for i in range(2,n):
		hcf=gcd(hcf,l[i])
	print(countDivisors(hcf))


import math
from collections import deque, defaultdict
from sys import stdin, stdout
input = stdin.readline
# print = stdout.write
listin = lambda : list(map(int, input().split()))
mapin = lambda : map(int, input().split())
n = int(input())
a = listin()
z = a[0]
for i in range(1, n):
    z = math.gcd(z, a[i])
d = defaultdict(int)
while(z%2 == 0):
    z//=2
    d[2]+=1
for i in range(3, int(z**0.5) + 1, 2):
    while(z%i == 0):
        z//=i
        d[i]+=1
if z > 1:
    d[z]+=1
ans = 1
for i in d.values():
    ans*=(i+1)
print(ans)

import math
import collections

def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            ass.append(i)
            n = n//i
    if n != 1:
        ass.append(n)
    return ass

n = int(input())
nums = list(map(int, input().split(" ")))

g = nums[0]
for i in range(1, n):
    g = math.gcd(g, nums[i])

primes = prime_factor(g)
c = collections.Counter(primes)

out = 1
for val in c.values():
    out *= (val+1)

print(out)