Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
input = sys.stdin.readline

import itertools

import math

from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def main():
    k = int(input())

    num_li = list(range(1, k+1))

    ans = 0

    old_dict = {}

    for l in itertools.product(num_li, repeat=3):

        str_l = str(sorted(l))

        if str_l in old_dict:
            ans += old_dict[str_l]
        else:
            num = gcd(l[0], l[1], l[2])
            old_dict[str_l] = num
            ans += num

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

import math

def main():
    k = int(input())

    ans = 0

    for i in range(1, k+1):
        for j in range(1, k+1):
            for l in range(1, k+1):
                ans += math.gcd(math.gcd(i,j),l)

    print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
s = input()

r = []
g = []
b = []

for i in range(n):
    if s[i] == "R":
        r.append(i)
    elif s[i] == "G":
        g.append(i)
    else:
        b.append(i)

sum = 0


for i in range(len(r)):
    for j in range(len(g)):
        for k in range(len(b)):
            index = [r[i],g[j],b[k]]
            index.sort()
            if index[1] - index[0] != index[2] - index[1]:
                sum += 1

print(sum)

### FIXED CODE ###

n = int(input())
s = list(input())

r = 0
g = 0
b = 0

for i in range(n):
    if s[i] == "R":
        r += 1
        s[i] = 1
    elif s[i] == "G":
        g += 1
        s[i] = 2
    else:
        b += 1
        s[i] = 4

cnt = r*g*b

for i in range(n):
    for j in range(i+1, n):
        k = 2 * j - i
        if k < n:
            if s[i] + s[j] + s[k] == 7:
                cnt -= 1

print(cnt)
### BUGGY CODE ###

H, W = map(int, input().split())
field = [input() for i in range(H)]
verti_lamp = [[0]*W for i in range(H)]
horiz_lamp = [[0]*W for i in range(H)]


def verti_search(y, x):
    count = 0
    down = 1
    while y+down <= H-1 and field[y+down][x] =='.':
        count += 1
        down += 1
    y += down
    return count, y


def horiz_search(y, x):
    count = 0
    right = 1
    while x+right <= W-1 and field[y][x+right] =='.':
        count += 1
        right += 1
    x += right
    return count, x


for y in range(H):
    x = 0
    while x <= W-1:
        if field[y][x] == '#':
            x += 1
            continue
        else:
            horiz, nx = horiz_search(y, x)
            for t in range(x, nx):
                horiz_lamp[y][t] = horiz
            x = nx

for x in range(W):
    y = 0
    while y <= H-1:
        if field[y][x] == '#':
            y += 1
            continue
        else:
            verti, ny = verti_search(y, x)
            for t in range(y, ny):
                verti_lamp[t][x] = verti
            y = ny

ans = 0
for y in range(H):
    for x in range(W):
        candidate = verti_lamp[y][x] + horiz_lamp[y][x] + 1
        ans = max(ans, candidate)

print(ans)


### FIXED CODE ###

H, W = map(int, input().split())
field = [input() for i in range(H)]
verti_lamp = [[0]*W for i in range(H)]
horiz_lamp = [[0]*W for i in range(H)]


def verti_search(y, x):
    count = 0
    down = 1
    while y+down <= H-1 and field[y+down][x] =='.':
        count += 1
        down += 1
    y += down
    return count, y


def horiz_search(y, x):
    count = 0
    right = 1
    while x+right <= W-1 and field[y][x+right] =='.':
        count += 1
        right += 1
    x += right
    return count, x


for y in range(H):
    x = 0
    while x <= W-1:
        if field[y][x] == '#':
            x += 1
            continue
        else:
            horiz, nx = horiz_search(y, x)
            for t in range(x, nx):
                horiz_lamp[y][t] = horiz
            x = nx

for x in range(W):
    y = 0
    while y <= H-1:
        if field[y][x] == '#':
            y += 1
            continue
        else:
            verti, ny = verti_search(y, x)
            for t in range(y, ny):
                verti_lamp[t][x] = verti
            y = ny

ans = 0
for y in range(H):
    for x in range(W):
        candidate = verti_lamp[y][x] + horiz_lamp[y][x] + 1
        ans = max(ans, candidate)

print(ans)
### BUGGY CODE ###

from heapq import heappush,heappop

n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(n)]
ab.sort()

stock = []
ans = 0
for i in range(1,m+1):
    while ab and ab[0][0] <= i:
        a = ab.pop(0)
        heappush(stock,-a[1])
    if stock:
        ans += -heappop(stock)

print(ans)

### FIXED CODE ###

import sys
from heapq import heappush,heappop

n,m = map(int,input().split())
ab = []
for line in sys.stdin:
    a,b = map(int,line.split())
    if a <= m:
        ab.append([a,b])
ab.sort()

stock = []
ans = 0
for i in range(1,m+1):
    while ab and ab[0][0] <= i:
        a = ab.pop(0)
        heappush(stock,-a[1])
    if stock:
        ans += -heappop(stock)

print(ans)
### BUGGY CODE ###

# input
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# process/output
# A[i+k+]^A[i+k+1]=B[i]^B[i+1]となるkを求める
AX = [A[i]^A[i+1] for i in range(N-1)]
BX = [B[i]^B[i+1] for i in range(N-1)]
AX.append(A[N-1]^A[0])
BX.append(B[N-1]^B[0])

ans = []
for k in range(N):
    i = 0
    while i < N:
        j = i+k
        if j >= N:
            j -= N

        if not BX[i] == AX[j]:
            break
        i += 1
    
    if i == N:
        # kに対応するxを求める
        x = A[k]^B[0]
        print(k, x)


### FIXED CODE ###

# input
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# process/output
# A[i+k+]^A[i+k+1]=B[i]^B[i+1]となるkを求め,kからxを求める
AX = [A[i]^A[i-1] for i in range(N)]
AX += AX
BX = [B[i]^B[i-1] for i in range(N)]

#print(AX)
#print(BX)

# BXの頭と終わりが同じ数字の並びの場合、その数mを求める
m = 0
for i in range(1, N):
    if BX[m] == BX[i]:
        m += 1
    else:
        m = 0
#print(m)

i, j, k = 0, 0, 0
while k < N:
    while True:
        #print("i,j: {},{},{}".format(i,j,k))
        if AX[i] == BX[j]:
            if j == N-1:
                print(k, A[k]^B[0])
                i += 1
                j = m
                break
            i += 1
            j += 1
        elif j != 0:
            j -= 1
        else:
            i += 1
            break
    
    k = i-j
### BUGGY CODE ###

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

ans = 0
for i in range(n-1):
    for j in range(n-1-i):
        hoge = a[i]*a[i+1+j] % 1000000007
        ans = ans + hoge
        if ans >= 1000000007:
            ans = ans - 1000000007

print(ans)

### FIXED CODE ###

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

s = sum(a)
ans = 0
mod = 10 ** 9 + 7

for i in range(n-1):
    s -= a[i]
    ans += a[i] * s % mod

ans = ans % mod
print(ans)
### BUGGY CODE ###

def num(s,n,k):
  d,m,dm,dmc = 0,0,0,0
  for i,j in zip(s[n:],s[n-k:]):
    if j == 1:
      d -= 1
      dm -= m
    elif j == 2:
      m -= 1
    if i == 1:
      d += 1
    elif i == 2:
      m += 1
      dm += d
    elif i == 3:
      dmc += dm
  return dmc

def main():
  n = int(input())
  t = input()
  _ = input()
  s = [0]*n + [(x=='D') + (x=='M')*2 + (x=='C')*3 for x in t]
  l = list(map(int, input().split()))
  for k in l:
    print(num(s,n,k))

main()

### FIXED CODE ###

def num(s,n,k):
  d,m,dm,dmc = 0,0,0,0
  for i in range(n,n*2):
    x,y = s[i],s[i-k]
    if y == 68:
      d -= 1
      dm -= m
    elif y == 77:
      m -= 1
    if x == 68:
      d += 1
    elif x == 77:
      m += 1
      dm += d
    elif x == 67:
      dmc += dm
  return dmc

def main():
  n = int(input())
  s = [0]*n + list(map(ord, list(input())))
  _ = input()
  l = list(map(int, input().split()))
  for k in l:
    print(num(s,n,k))

main()
### BUGGY CODE ###

import collections as cc
n=int(input())
l=list(map(int,input().split()))
ff=cc.Counter(l)
ff=dict(ff)
ans=[]
for i in range(n):
    f=ff.copy()
    f[l[i]]=max(0,f[l[i]]-1)
    t=0
    for i in f:
        x=f[i]
        t+=(x*(x-1))//2
    ans.append(t)
for i in ans:
    print(i)
    
    


### FIXED CODE ###

import collections as cc
n=int(input())
l=list(map(int,input().split()))
ff=cc.Counter(l)
ff=dict(ff)
ans=0
for i in ff:
    x=ff[i]
    ans+=(x*(x-1))//2
v={}
for i in set(l):
    vv=max(ff[i]-1,0)
    te=ans-(ff[i]*(ff[i]-1))//2+(vv*(vv-1))//2
    v[i]=te
for i in l:
    print(v[i])
### BUGGY CODE ###

S = input()

c = 0
for keta in range(4, len(S)):
  for i in range(0, len(S)-keta+1):
    #print(int(S[i:i+keta]))
    if int(S[i:i+keta]) % 2019 == 0:
      c += 1
    
print(c)

### FIXED CODE ###

S = input()
Sr = S[::-1] # 一の位から考える

T = 0 # 部分文字列
mod = [0] * 2019 # mod数え上げ配列
mod[0] += 1 # 「部分文字列T = S」の場合の、 「0 % 2019 = 0」を予めカウント
d = 1 # 桁数
for i, s in enumerate(Sr):
  T += int(s) * d
  T %= 2019
  d = (d * 10) % 2019
  
  mod[T] += 1
  
# ペアを合計
# n個から2通り選ぶ（nC2）
mod = [n * (n-1) // 2 for n in mod]
print(sum(mod))
### BUGGY CODE ###

from functools import cmp_to_key
import math
import bisect

n = int(input())
s = input()
k = 1
rank = [0] * (n+1)
tmp = [0] * (n+1)
sa = [''] * (n+1)

def compare_sa(i,j):
	if rank[i] != rank[j]:
		return -1 if rank[i] < rank[j] else 1
	else:
		if i + k <= n:
			ri = rank[i+k]
		else:
			ri = -1
		if j + k <= n:
			rj = rank[j+k]
		else:
			rj = -1
		return -1 if ri < rj else 1


for i in range(n+1):
	sa[i] = i
	if i < n:
		rank[i] = ord(s[i])
	else:
		rank[i] = -1

while k <= n:

	sa = sorted(sa,key=cmp_to_key(compare_sa))

	tmp[sa[0]] = 0

	for i in range(1,n+1):
		if compare_sa(sa[i-1],sa[i]) == -1:
			tmp[sa[i]] = tmp[sa[i-1]] + 1
		else:
			tmp[sa[i]] = tmp[sa[i-1]]

	for i in range(n+1):
		rank[i] = tmp[i]

	k *= 2
"""
#saはインデックス、sorted_listは実際の文字列
sorted_list = []
for i in range(n+1):
	sorted_list.append(s[sa[i]:])
print(sa)
print(sorted_list)

#文字列検索
T = ['ab','abra','abc','abracadabra','abracadabraaa','brabra','bra']
for t in T:
	start = bisect.bisect_left(sorted_list,t)
	end = bisect.bisect_left(sorted_list,t[:-1]+chr(ord(t[-1])+1))
	if start == end:
		print(t+'は存在しません')
	else:
		print(t+'は存在します')
"""

#lcp配列の作成
def getLCP(i,j):
	h = 0
	while i+h < n and j+h < n:
		if s[j+h] != s[i+h]:
			break
		h+=1
	return h

#lcp配列の最大値=最長の共通部分文字列のインデックス
#ans = sorted_list[ lcp.index(max(lcp)) ]
#ans = ans[:max(lcp)]
#print(ans)

ans = 0
for i in range(0,n):
	for j in range(i+1,n):
		lcp = min(getLCP(i,j),j-i)
		ans = max(ans,lcp)

print(ans)


### FIXED CODE ###

n = int(input())
s = input()

def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
        	j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A
ans = 0
for i in range(n-1):
	tmp = z_algo(s[i:])
	for j,zj in enumerate(tmp):
		if j+1 > zj:
			ans = max(ans,zj)

print(ans)
### BUGGY CODE ###

s=int(input())
t=input()
a=0
b=0
c=0
d=[]
e=[]
f=[]
for i in range(s):
  if t[i]=='R':
    a=a+1
    d.append(i)
  elif t[i]=='G':
    b=b+1
    e.append(i)
  else:
    c=c+1
    f.append(i)
g=a*b*c
for j in range(len(d)):
  for k in range(len(e)):
    for l in range(len(f)):
      p=max(d[j],e[k],f[l])
      q=min(d[j],e[k],f[l])
      r=d[j]+e[k]+f[l]
      r=r-p-q
      if 2*r==p+q:
        g=g-1
print(g)

### FIXED CODE ###

s=int(input())
t=input()
a=0
b=0
c=0
for i in range(s):
  if t[i]=='R':
    a=a+1
  elif t[i]=='G':
    b=b+1
  else:
    c=c+1
g=a*b*c
for j in range(s):
  for k in range(j+1,s):
    p=2*k-j
    if p>s-1:
      break
    if t[j]!=t[k] and t[p]!=t[k] and t[p]!=t[j]:
      g=g-1
print(g)
### BUGGY CODE ###

import numpy as np

n = int(input())
a = np.concatenate([np.array([0]),np.array(list(map(int,input().split())))])

for i in range(n):
  ans = np.sum(np.where(a == (i+1),1,0))
  print(ans)

### FIXED CODE ###

import numpy as np

n = int(input())
base = np.zeros(n)
a = np.array(list(map(int,input().split())))

for i in range(n-1):
  base[a[i]-1] += 1
  
for i in range(n):
  print(int(base[i]))
### BUGGY CODE ###

n = int(input())
a = []

while n%2 == 0:
    a.append(2)
    n //= 2

f = 3
while f**2 <= n:
    while n%f == 0:
        a.append(f)
        n //= f
    f += 2
if n != 1:
    a.append(n)

ans, num = 0, len(a)
diff = float('inf')
for i in range(2**num):
    b = ['-']*num
    c0, c1 = 1, 1
    for j in range(num):
        if ((i>>j)&1):
            b[num-1-j] = '+'
    for k in range(num):
        if b[k] == '+':
            c0 *= a[k]
        else:
            c1 *= a[k]
    if abs(c0-c1) < diff:
        ans = max(len(str(c0)), len(str(c1)))
        diff = abs(c0-c1)
print(ans)


### FIXED CODE ###

n = int(input())
i, ans = 1, 0

while i**2 <= n:
    if n%i == 0:
        num = n//i
        ans = max(len(str(num)), len(str(i)))
    i += 1
print(ans)
### BUGGY CODE ###

n = int(input())
li = list(map(int, input().split()))

if 0 in li:
    print(0)
    exit()

ans = 1
for i in li:
    ans *= i

if ans > 10 ** 18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

n = int(input())
li = list(map(int, input().split()))

if 0 in li:
    print(0)
    exit(0)

ans = 1
for i in li:
    ans *= i
    if ans > 10 ** 18:
        print(-1)
        exit(0)

print(ans)
### BUGGY CODE ###

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

c = [0] * (n+1)
j = 0
if 1 not in s:
    print(-1)
elif len(s) == 1:
    print(0)
else:
    for i in range(1,n+1):
        if i in s:
            c[i] = s.index(i)
            del s[j:c[i]]
            j += 1
            #print(s)
        elif i not in s:
            if len(s) == j:
                break
            else:
                while len(s) != j:
                    s.pop()
    print(n - len(s))

### FIXED CODE ###

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

c = []
j = 0
if 1 not in s:
    print(-1)
elif len(s) == 1:
    print(0)
else:
    for i in s:
        if i - j == 1:
            j = i
            c.append(i)
    print(n - len(c))
### BUGGY CODE ###

import sys
from bisect import bisect_left
inpurt = sys.stdin.readline
a, b, q = map(int, input().split())
INF = 10 ** 11
s = [-INF]
s_append = s.append
for i in range(a):
    si = int(input())
    s_append(si)
s_append(INF)
t = [-INF]
t_append = t.append
for i in range(b):
    ti = int(input())
    t_append(ti)
t_append(INF)
x = []
x_append = x.append
for i in range(q):
    xi = int(input())
    x_append(xi)

for xi in x:
    index_s = bisect_left(s, xi)
    s1 = xi - s[index_s - 1]
    s2 = s[index_s] - xi
    index_t = bisect_left(t, xi)
    t1 = xi - t[index_t - 1]
    t2 = t[index_t] -xi
    print(min(max(s1, t1), max(s2, t2), min(s1, t2) * 2 + max(s1, t2), min(s2, t1) * 2 + max(s2, t1)))


### FIXED CODE ###

import sys
from bisect import bisect_left
inpurt = sys.stdin.readline
a, b, q = map(int, input().split())
INF = 10 ** 11
s = [-INF]
s_append = s.append
for i in range(a):
    si = int(input())
    s_append(si)
s_append(INF)
t = [-INF]
t_append = t.append
for i in range(b):
    ti = int(input())
    t_append(ti)
t_append(INF)
x = []
x_append = x.append
for i in range(q):
    xi = int(input())
    x_append(xi)

for xi in x:
    index_s = bisect_left(s, xi)
    s1 = xi - s[index_s - 1]
    s2 = s[index_s] - xi
    index_t = bisect_left(t, xi)
    t1 = xi - t[index_t - 1]
    t2 = t[index_t] -xi
    print(min(max(s1, t1), max(s2, t2), min(s1, t2) * 2 + max(s1, t2), min(s2, t1) * 2 + max(s2, t1)))
### BUGGY CODE ###

s=input()
n=len(s)
ans=0
for i in range(n-3):
    for j in range(i+5,n+1):
        if (int(s[i:j])%2019==0):
            ans+=1
print(ans)

### FIXED CODE ###

S=input()[::-1]
List=[0]*2019
ans=0
a=1
d=0

for s in S:
  d=d+int(s)*a
  List[d%2019]+=1
  a=a*10
  a=a%2019
  #print(s[i:],int(s[i:])%2019)
  
#print(List)
ans=List[0]
for i in List:
  if (i>=2):
    ans+=(i*(i-1))//2
  
print(ans)
### BUGGY CODE ###

class UnionFind():
    # コンストラクタ
    def __init__(self, n):
        # 要素数
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        self.parents = [-1] * n

    # 要素xが属するグループの根を返す(経路圧縮)
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # 要素xが属するグループと要素yが属するグループとを併合する
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y: return

        if self.parents[x] > self.parents[y]: x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]

    # 要素x,yが同じグループに属するかどうかを返す
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 要素xが属するグループに属する要素をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    # 全ての根の要素をリストで返す
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    # グループの数を返す
    def group_count(self):
        return len(self.roots())

    # 辞書{根の要素: [そのグループに含まれる要素のリスト], ...}を返す
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

N,M = map(int, input().split())
UF = UnionFind(N)

cnt = 0
for _ in range(M):
    a, b = map(int, input().split())
    UF.union(a - 1, b - 1)

ans = 0
for c in UF.all_group_members().values():
    ans = max(ans, len(c))

print(ans)

### FIXED CODE ###

class UnionFind():
    # コンストラクタ
    def __init__(self, n):
        # 要素数
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        self.parents = [-1] * n

    # 要素xが属するグループの根を返す(経路圧縮)
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # 要素xが属するグループと要素yが属するグループとを併合する
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y: return

        if self.parents[x] > self.parents[y]: x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]

    # 要素x,yが同じグループに属するかどうかを返す
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 要素xが属するグループに属する要素をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    # 全ての根の要素をリストで返す
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    # グループの数を返す
    def group_count(self):
        return len(self.roots())

    # 辞書{根の要素: [そのグループに含まれる要素のリスト], ...}を返す
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

N,M = map(int, input().split())
UF = UnionFind(N)

cnt = 0
for _ in range(M):
    a, b = map(int, input().split())
    UF.union(a - 1, b - 1)

ans = 0
for c in UF.roots():
    ans = max(ans, UF.size(c))

print(ans)
### BUGGY CODE ###

N = int(input())
S = input()

R = []
G = []
B = []
ans = 0

for i, x in enumerate(S):
  if x == 'R':
    R.append(i)
  elif x == 'G':
    G.append(i)
  else:
    B.append(i)
    
for r in R:
  for g in G:
    for b in B:
      lis = sorted([r, g, b])
      if lis[1] - lis[0] != lis[2] - lis[1]:
        ans += 1
        
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
 
r_cnt = s.count('R')
g_cnt = s.count('G')
b_cnt = s.count('B')
 
ans = r_cnt * g_cnt * b_cnt
 
for i in range(n):
    for d in range(n):
        j = i + d
        k = j + d
        if k >= n:break
        if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            ans -= 1
 
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np


def is_prime(a):
    flg = 1

    for i in range(2, a // 2 + 1):
        if is_prime(i) == 1:
            if a % i == 0:
                flg = -1
                break

    return flg


a, b = map(int, input().split())

if a > b:
    max_num = a // 2
else:
    max_num = b // 2

ans = 1

for i in range(2, max_num // 2):
    if is_prime(i) == 1:
        if a % i == 0 and b % i == 0:
            ans += 1

print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np

a, b = map(int, input().split())

soin_a = np.array([], dtype='int')
for i in range(2, int(np.sqrt(a)) + 1):
    if a % i == 0:
        soin_a = np.append(soin_a, i)
        while a % i == 0:
            a //= i
if a != 1:
    soin_a = np.append(soin_a, a)

soin_b = np.array([], dtype='int')
for i in range(2, int(np.sqrt(b)) + 1):
    if b % i == 0:
        soin_b = np.append(soin_b, i)
        while b % i == 0:
            b //= i
if b != 1:
    soin_b = np.append(soin_b, b)

ans = 1
for j in soin_a:
    if soin_b[soin_b == j].size != 0:
        ans += 1

print(ans)
### BUGGY CODE ###

from bisect import bisect_left, bisect_right
import sys
import numpy as np
input = sys.stdin.readline
N,D,A=map(int, input().split())
mg = [None]*N
X = [None]*N
H = [None]*N
XD = [None]*N
for i in range(N):
  mg[i]=list(map(int, input().split()))
mg.sort(key=lambda x:x[0])
mg = (np.array(mg)).T
X = mg[0]
H = mg[1]
for i in range(N):
  XD[i] = bisect_right(X[i+1:],X[i]+2*D) + (i+1)
XD = np.array(XD)
i = 0
ans = 0
while i<N:
  if H[i]>0:
    k = (H[i]+A-1)//A
    ans +=k
    H[i:XD[i]]=np.maximum(0,H[i:XD[i]]-k*A)
  i+=1
print(ans)

### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

from bisect import bisect_left, bisect_right

n, d, a = map(int, input().split())
x = []
xh = dict()
for _ in range(n):
    xi, hi = map(int, input().split())
    x.append(xi)
    xh[xi] = hi
x.sort()

l = 0
ret = 0
ai = [0] * (n+1)
anow = 0
while l < n:
    xl = x[l]
    hl = xh[xl]
    anow += ai[l]
    hl -= a * anow
    if hl > 0:
        r = bisect_right(x, xl+2*d)
        k = (hl+(a-1))//a
        ret += k
        anow += k
        ai[r] -= k
    l += 1
print(ret)
### BUGGY CODE ###

def main():
    mod = 10**9+7
    inv_n = [0]*1001
    nCr = [[0]*(i+1) for i in range(1001)]
    for i in range(1001):
        inv_n[i] = pow(i, mod-2, mod)
    for i in range(1001):
        nCr[i][0] = 1
        nCr[i][i] = 1
    for i in range(2, 1001):
        for j in range(1, i):
            nCr[i][j] = (nCr[i-1][j-1]+nCr[i-1][j]) % mod

    n, a, b, c, d = map(int, input().split())
    f = dict()
    for N in range(1, n+1):
        for A in range(a, b+1):
            if N-c*A < 0:
                break
            temp = 1
            for C in range(1, c):
                temp = temp*nCr[N-(C-1)*A][A]*inv_n[C] % mod
            for C in range(c, d+1):
                if N-C*A < 0:
                    break
                temp = temp*nCr[N-(C-1)*A][A]*inv_n[C] % mod
                f[(N, A, C)] = temp

    dp = [0]*(n+1)
    dp[0] = 1

    for A in range(a, b+1):
        dp2 = [i for i in dp]
        for C in range(c, d+1):
            for i in range(n):
                N = n-i
                if i+C*A > n:
                    break
                dp2[i+C*A] = (dp2[i+C*A]+f[(N, A, C)]*dp[i]) % mod
        dp = dp2
    print(dp[-1])


main()


### FIXED CODE ###

def main():
    mod = 10**9+7
    inv_n = [0]*1001
    nCr = [[1]*(i+1) for i in range(1001)]
    for i in range(1001):
        inv_n[i] = pow(i, mod-2, mod)
    for i in range(2, 1001):
        for j in range(1, i):
            nCr[i][j] = (nCr[i-1][j-1]+nCr[i-1][j]) % mod
    n, a, b, c, d = map(int, input().split())
    dp = [0]*(n+1)
    dp[0] = 1

    for A in range(b, a-1, -1):
        dp2 = [i for i in dp]
        for N in range(n-c*A, -1, -1):
            e = dp[N]
            if e:
                temp = 1
                for C in range(1, c):
                    temp = temp*nCr[n-N-(C-1)*A][A]*inv_n[C] % mod
                for C in range(c, min(d, (n-N)//A)+1):
                    temp = temp*nCr[n-N-(C-1)*A][A]*inv_n[C] % mod
                    dp2[N+C*A] = (dp2[N+C*A]+temp*e) % mod
        dp = dp2
    print(dp[-1])


main()