Vova again tries to play some computer card game.

The rules of deck creation in this game are simple. Vova is given an existing deck of n cards and a magic number k. The order of the cards in the deck is fixed. Each card has a number written on it; number a_{i} is written on the i-th card in the deck.

After receiving the deck and the magic number, Vova removes x (possibly x = 0) cards from the top of the deck, y (possibly y = 0) cards from the bottom of the deck, and the rest of the deck is his new deck (Vova has to leave at least one card in the deck after removing cards). So Vova's new deck actually contains cards x + 1, x + 2, ... n - y - 1, n - y from the original deck.

Vova's new deck is considered valid iff the product of all numbers written on the cards in his new deck is divisible by k. So Vova received a deck (possibly not a valid one) and a number k, and now he wonders, how many ways are there to choose x and y so the deck he will get after removing x cards from the top and y cards from the bottom is valid?


-----Input-----

The first line contains two integers n and k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ 10^9).

The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9) — the numbers written on the cards.


-----Output-----

Print the number of ways to choose x and y so the resulting deck is valid.


-----Examples-----
Input
3 4
6 2 8

Output
4

Input
3 6
9 1 14

Output
1



-----Note-----

In the first example the possible values of x and y are:

  x = 0, y = 0;  x = 1, y = 0;  x = 2, y = 0;  x = 0, y = 1.

Difficulty: interview

Starter code:

Solutions:
n,k=map(int,input().split())
l=list(map(int,input().split()))
pf=[]
needed=[]
for i in range(2,40000):
	if k%i==0:
		pf.append(i)
		c=0
		while k%i==0:
			k//=i
			c+=1
		needed.append(c)
if k>1:
	pf.append(k)
	needed.append(1)
pfl=len(pf)
cnt=[[0]*n for i in range(pfl)]
for i in range(n):
	for j in range(len(pf)):
		c=0
		while l[i]%pf[j]==0:
			c+=1
			l[i]//=pf[j]
		cnt[j][i]=c
have=[sum(i) for i in cnt]
pos=n
def ok():
	for i in range(len(pf)):
		if have[i]<needed[i]:
			return False
	return True
if not ok():
	print(0)
	quit()
for i in range(n-1,0,-1):
	for j in range(len(pf)):
		have[j]-=cnt[j][i]
	if not ok():
		for j in range(len(pf)):
			have[j]+=cnt[j][i]
		break
	pos=i
ans=n-pos+1
for x in range(n-1):
	for j in range(len(pf)):
		have[j]-=cnt[j][x]
	if pos==(x+1):
		for j in range(len(pf)):
			have[j]+=cnt[j][pos]
		pos+=1
	while pos<n:
		if ok():
			break
		else:
			for i in range(len(pf)):
				have[i]+=cnt[i][pos]
			pos+=1
	if ok():
		ans+=n-pos+1
	else:
		break
print(ans)

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

n,k = [int(x) for x in input().split()]
a = [gcd(int(x),k) for x in input().split()]

if k == 1:
  print(((n+1)*(n+2))//2-n-1)
else:
  s = 0
  e = 0
  total = ((n+1)*(n+2))//2-1-n
  #print(total)
  #extra = {}
  c = 1
  
  while e < n:
    flag = False
    while c%k != 0 and e < n:
      total -= e-s
      c *= a[e]
      e += 1
    while c%k == 0 and s < e:
      c //= a[s]
      s += 1
  total -= e-s
  print(total)


import sys


def get_primes(n: int):
    from itertools import chain
    from array import array
    primes = {2, 3}
    is_prime = (array('b', (0, 0, 1, 1, 0, 1, 0)) +
                array('b', (1, 0, 0, 0, 1, 0))*((n-1)//6))

    for i in chain.from_iterable((list(range(5, n+1, 6)), list(range(7, n+1, 6)))):
        if is_prime[i]:
            primes.add(i)
            for j in range(i*3, n+1, i*2):
                is_prime[j] = 0

    return is_prime, primes


n, k = list(map(int, input().split()))
cards = list(map(int, input().split()))
_, primes = get_primes(32000)

div, div_cnt = [], []
for p in primes:
    if k % p == 0:
        div.append(p)
        div_cnt.append(0)
        while k % p == 0:
            div_cnt[-1] += 1
            k //= p
if k > 1:
    div.append(k)
    div_cnt.append(1)

m = len(div)
acc = [[0]*m for _ in range(n+1)]

for i, x in enumerate(cards, start=1):
    for j in range(m):
        acc[i][j] += acc[i-1][j]
        while x % div[j] == 0:
            acc[i][j] += 1
            x //= div[j]

ans = 0
j = 0
for i in range(n):
    j = max(j, i+1)
    while j <= n and any(acc[j][k]-acc[i][k] < div_cnt[k] for k in range(m)):
        j += 1
    if j > n:
        break
    ans += n - j + 1

print(ans)