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

n = int(input())

sum = ((n - 1) * n) / 2

max_mod = 0
iw = 0
for i in range(n):
  if i == 0:
    continue
  mod_i = n % i
  if mod_i > max_mod:
    max_mod = mod_i
    iw = i

if max_mod > iw:
  sum = (sum - iw) + max_mod

print(int(sum))



### FIXED CODE ###

n = int(input())

sum = ((n - 1) * n) // 2

print(sum)
### BUGGY CODE ###

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

import fractions
from functools import reduce

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)


ans=0
GCD_target=gcd_list(A)
#print("GCD_target = {}".format(GCD_target))

for i in range(N):
   #copied_A = A[:]
   remove=A.pop(i)
   GCD_current=gcd_list(A)
   A.insert(i,remove)
   #print(GCD_current)
   ans=max(ans,GCD_current)

print(ans)

### FIXED CODE ###

from fractions import *
n = int(input())
a = [0]+list(map(int, input().split()))+[0]
b = [0]*(n+2)
c = [0]*(n+2)
for i in range(1, n+1):
	b[i] = gcd(b[i-1], a[i])
for i in range(n, 0, -1):
	c[i] = gcd(c[i+1], a[i])

ans=1
for i in range(1, n+1):
    x1 = b[i-1]
    x2 = c[i+1]
    ans=max(ans, gcd(x1, x2))

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

n=int(input())
li = list(map(int,input().split()))
for i in range(1,n+1):
    print(li.count(i))


### FIXED CODE ###

n=int(input())
li=list(map(int,input().split()))
ans=[0]*n
check=1
for i in range(len(li)):
    ans[li[i]-1]+=1
for i in range(len(ans)):
  print(ans[i])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

def main():
    inp = [int(x) for x in sys.stdin.buffer.read().split()]
    n, m = inp[0],inp[1]

    w, v = inp[2::2], inp[3::2]

    dp = [0] * (m + 1)
    for j in range(w[0], m + 1):
        dp[j] = v[0]

    for i in range(n - 1):
        vi = v[i + 1]
        wi = w[i + 1]
        for j in reversed(range(wi, m + 1)):
            dp[j] = max(vi + dp[j - wi], dp[j])

    print(dp[-1])
main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys, os
range = xrange

def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n, m = inp[0],inp[1]

    w, v = inp[2::2], inp[3::2]

    dp = [0] * (m + 1)
    for j in range(w[0], m + 1):
        dp[j] = v[0]

    for i in range(n - 1):
        vi = v[i + 1]
        wi = w[i + 1]
        for j in reversed(range(wi, m + 1)):
            dp[j] = max(vi + dp[j - wi], dp[j])

    print(dp[-1])
main()
### BUGGY CODE ###

import heapq

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

ch -= 1; cw -= 1; dh -= 1; dw -= 1; 

s = []
for _ in range(H):
    s.append(list(input()))
cs = [[1000000 for _ in range(W)] for _ in range(H)]

q = []
heapq.heappush(q, (0, (ch, cw)))

while q:
    c, (h, w) = heapq.heappop(q)
    if cs[h][w] <= c:
        continue
    cs[h][w] = c
    for nh, nw in [(h - 1, w), (h + 1, w), (h, w - 1), (h, w + 1)]:
        if 0 <= nh < H and 0 <= nw < W and s[nh][nw] == '.' and c < cs[nh][nw]:
            heapq.heappush(q, (c, (nh, nw)))
    for nh in range(h - 2, h + 3):
        for nw in range(w - 2, w + 3):
            if 0 <= nh < H and 0 <= nw < W and s[nh][nw] == '.' and c + 1 < cs[nh][nw]:
                heapq.heappush(q, (c + 1, (nh, nw)))

print(-1 if cs[dh][dw] == 1000000 else cs[dh][dw])


### FIXED CODE ###

import heapq

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

ch -= 1; cw -= 1; dh -= 1; dw -= 1; 

s = []
for _ in range(H):
    s.append(list(input()))
cs = [[1000000 for _ in range(W)] for _ in range(H)]

q = []
heapq.heappush(q, (0, (ch, cw)))

while q:
    c, (h, w) = heapq.heappop(q)
    if cs[h][w] < c:
        continue
    cs[h][w] = c
    for nh, nw in [(h - 1, w), (h + 1, w), (h, w - 1), (h, w + 1)]:
        if 0 <= nh < H and 0 <= nw < W and s[nh][nw] == '.' and c < cs[nh][nw]:
            cs[nh][nw] = c
            heapq.heappush(q, (c, (nh, nw)))
    for nh in range(h - 2, h + 3):
        for nw in range(w - 2, w + 3):
            if 0 <= nh < H and 0 <= nw < W and s[nh][nw] == '.' and c + 1 < cs[nh][nw]:
                cs[nh][nw] = c + 1
                heapq.heappush(q, (c + 1, (nh, nw)))

print(-1 if cs[dh][dw] == 1000000 else cs[dh][dw])
### BUGGY CODE ###

def comp(a, b, c):
    if ( (a < b+c)
     and (b < c+a)
     and (c < a+b)):
        return True
    else:
        return False

n = int(input())
l = []
l[:] = map(int,input().split())

c = 0
for i in range(0,n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            if(comp(l[i], l[j], l[k])):
                c+=1
print(c)


### FIXED CODE ###

from bisect import bisect_right

n = int(input())
l = list(map(int,input().split()))
l.sort() # 昇順にソート

count = 0
for i in range(0,n-2):
    a = l[i]
    for j in range(i+1, n-1):
        ab = a+l[j]
        # bisect_left(a, x): x を a に挿入できる点を返す
        # cの最大値は a+b-1
        k = bisect_right(l, ab-1, j+1, n)
        count += k-(j+1)
print(count)
### BUGGY CODE ###

import numpy as np

N = int(input())
P = np.array(input().split(' '), dtype = int)
# P = list(map(int, input().split(' ')))

print(np.sum(np.array([np.sum(P[:i+1] >= P[i]) == i+1 for i in range(N)])))

### FIXED CODE ###

N = int(input())
# P = np.array(input().split(' '), dtype = int)
P = list(map(int, input().split(' ')))

p_min = P[0]
ans = 0
for p in P:
    if p <= p_min:
        p_min = p
        ans += 1
print(ans)
### BUGGY CODE ###

S = str(input())
T = str(input())
alp = "abcdefghijklmnopqrstuvwxyz"
for i in range(0,min(len(S),10**5)):
  if S[i] != T[i]:
    S = S.translate(str.maketrans({S[i]:T[i], T[i]:S[i]}))
  if S == T:
    print("Yes")
    exit()
print("No")

### FIXED CODE ###

S = str(input())
T = str(input())
alp = "abcdefghijklmnopqrstuvwxyz"
for i in range(0,min(len(S),len(alp)*2)):
  if S[i] != T[i]:
    S = S.translate(str.maketrans({S[i]:T[i], T[i]:S[i]}))
  else:
    pass
  if S == T:
    print("Yes")
    exit()
print("No")
### BUGGY CODE ###

n = int(input())
s = list(input())
big_num = 10 ** 6

for i in range(n):
    west = s[:i].count("W")
    east = s[i+1:].count("E")
    if big_num > west + east:
        big_num = west + east
        
print(big_num)

### FIXED CODE ###

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

ruisekiwa = [0]
ans = n

for i in s:
    if i == "W":
        ruisekiwa.append(ruisekiwa[-1]+1)
    else:
        ruisekiwa.append(ruisekiwa[-1])
        
for i in range(1,n+1):
    w = ruisekiwa[i-1]
    e = n-i-(ruisekiwa[-1]-ruisekiwa[i])
    ans = min(ans,w+e)
    
print(ans)
### BUGGY CODE ###

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import bisect
import sys
sys.setrecursionlimit(10**6)
mod=998244353
n=i1() 
d=[]
for i in range(n):
  d.append(i2())
d=sorted(d)
dx=[]
dd=[]
for i,j in d:
  dx.append(i)
  dd.append(j)
r=[]
dt=[-1 for i in range(n)]

def ddd(i,dt):
  x=i
  for k in range(i+1,n):
      if dx[k]<dx[i]+dd[i] and dt[k]<0:
         xx,dt=ddd(k,dt)
         x=max(x,xx)
  dt[i]=x
  return x,dt
for i in range(n):
    if dt[i]<0:
      x,dt=ddd(i,dt)
dp=[0 for i in range(n+1)]
dp[-1]=1
for i in range(n)[::-1]:
  dp[i]+=dp[i+1]
  dp[i]+=dp[dt[i]+1]
  dp[i]%=mod
print(dp[0])    

### FIXED CODE ###

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import bisect
mod=998244353
n=int(input())
d=[]
N=1<<(n.bit_length())
t=[-1 for i in range(2*N-1)]

def ud(i,x):
  i+=N-1
  t[i]=x
  while i:
    i=(i-1)>>1
    if t[i*2+1]>t[i*2+2]:t[i]=t[i*2+1]
    else:t[i]=t[i*2+2]
     

def qr(a,b):
    a+=N-1
    b+=N-1
    L = -1
    R = -1
    while a < b:
      if a&1==0:
         if L<t[a]:L = t[a]
      if b&1==0:
         b-=1
         if R<t[b]:R = t[b]
      
      a>>=1
      b>>=1
      
         
    return max(L, R)
 
for i in range(n):
  d.append([int(i) for i in input().split()])
d.sort()
dx=[]
dd=[]
for i,j in d:
  dx.append(i)
  dd.append(j)
for i in range(n)[::-1]:
 tx=dx[i]+dd[i]
 j=bisect.bisect_left(dx,tx)
 tt=qr(i,j)
 if j-1>tt:ud(i,j-1)
 else:ud(i,tt)
dp=[0 for i in range(n+1)]
dp[-1]=1
for i in range(n)[::-1]:
  dp[i]+=dp[i+1]
  dp[i]%=mod
  dp[i]+=dp[t[i+N-1]+1]
  dp[i]%=mod
print(dp[0])
### BUGGY CODE ###

from heapq import heappush, heappop
from collections import defaultdict
import sys
input = sys.stdin.readline

N, M, L = map(int, input().split())
inf = float("inf")
d = defaultdict(list)

for _ in range(M):
    A, B, C = map(int, input().split())
    if C>L:continue
    d[A-1].append((B-1, C))
    d[B-1].append((A-1, C))

charged_dict = [[(inf,inf)]*N for _ in range(N)]
for j in range(N):
    charged_dict[j][j] = (0, 0)
    q = [(0, 0, j)]
    while q:
        charged, used, u = heappop(q)
        if (charged, used) > charged_dict[j][u]:
            continue
        for v, next_cost in d[u]:
            c = (charged+1, next_cost) if used+next_cost>L else (charged, used+next_cost)
            if charged_dict[j][v] > c:
                charged_dict[j][v] = c
                heappush(q, c+(v,))

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    ans = charged_dict[s-1][t-1][0]
    print(ans if ans!=inf else -1)

### FIXED CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

N, M, L = map(int, input().split())
inf = 10**15
V = [[] for _ in range(N)]

for _ in range(M):
    A, B, C = map(int, input().split())
    if C>L:continue
    V[A-1].append((B-1, C))
    V[B-1].append((A-1, C))

dists = []
for i in range(N):
    dist = [(inf,inf)] * N
    dist[i] = (0, 0)
    u = [False] * N
    for _ in range(N):
        (charged, used), j = min([(dist[i], i) for i in range(N) if not u[i]])
        u[j] = True
        for k, next_cost in V[j]:
            if j==k: continue
            c = (charged+1, next_cost) if used+next_cost>L else (charged, used+next_cost)
            if dist[k] > c:
                dist[k] = c
    dists.append(dist)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    ans = dists[s-1][t-1][0]
    print(ans if ans!=inf else -1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

n,k = list(map(int, list(input().split())))
scores = list(map(int, list(input().split())))

s_k = 1
for j in range(k):
    s_k *= scores[j]

for i in range(k + 1, n + 1):
    _s_k = s_k
    remove = scores[i - k - 1]
    add    = scores[i - 1]
    s_k = s_k * add / remove

    if _s_k < s_k:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

# -*- coding: utf-8 -*-

n,k = list(map(int, list(input().split())))
scores = list(map(int, list(input().split())))

for i in range(k + 1, n + 1):
    remove = scores[i - k - 1]
    add    = scores[i - 1]

    if remove < add:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n = int(input())
u = list(map(int,input().split()))
m = list(map(int,input().split()))
d = list(map(int,input().split()))

cnt = 0
for i in range(n):
    for j in range(n):
        if m[j] < d[i]:
            for k in range(n):
                if u[k] < m[j]:
                    cnt += 1
print(cnt)

### FIXED CODE ###

import bisect

n = int(input())
u = list(map(int,input().split()))
m = list(map(int,input().split()))
d = list(map(int,input().split()))
u.sort()
m.sort()
d.sort()

ans = 0
for a in m:
    ans += bisect.bisect_left(u,a) * (n - bisect.bisect_right(d,a))
print(ans)
### BUGGY CODE ###

import itertools
K=int(input())

result=[]
count=0
cnt=0
def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a

 
for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      ans1=gcd(j,k)
      count=gcd(i,ans1)
      cnt+=count
      
print(cnt)



### FIXED CODE ###

from math import gcd
K=int(input())

result=[]
count=0
cnt=0
# def gcd(a,b):
#   while b!=0:
#     a,b=b,a%b
#   return a

 
for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      cnt+=gcd(gcd(i,j),k)


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

from copy import copy
N = int(input())
al = [int(a) for a in input().split()]

def gcd(a, b):
    while b > 0:
        a, b = b, a%b
    return a
  
ans_l = [0]*N

for i in range(N):
    tmp2 = copy(al)
    del tmp2[i]
    a = tmp2[0]
    for j in range(N-1):
        a = gcd(a, tmp2[j])
    ans_l[i] = a

print(max(ans_l))

### FIXED CODE ###

N = int(input())
al = [int(a) for a in input().split()]
      
def gcd(a, b):
    while b > 0:
        a, b = b, a%b
    return a

l = [0]*N
r = [0]*N

# 左から右
for i in range(N-1):
    if i == 0:
        a = al[i]
        l[i+1] = a
    if i >= 1:
        a = gcd(a, al[i])
        l[i+1] = a

# 右から左
for i in range(N-1):
    if i == 0:
        a = al[-i-1]
        r[-i-2] = a
    if i >= 1:
        a = gcd(a, al[-i-1])
        r[-i-2] = a

# 最大公約数リスト
ansl = [0]*N
for i in range(N):
    if i == 0:
        ansl[i] = r[i]
    elif i == N-1:
        ansl[i] = l[i]
    else:
        ansl[i] = gcd(r[i], l[i])
print(max(ansl))
### BUGGY CODE ###

n,s=open(0)
n=int(n)
a=0
for i in range(n):
  t=0
  for v,w in zip(s,s[i:n]):
    t=-~t*(v==w)
    if t>i:break
    if t>a:a=t
print(a)

### FIXED CODE ###

from subprocess import*
with open('e.cpp','w')as f:f.write(r"""
#include<iostream>
using namespace std;
main(){
  int n;
  string s;
  cin>>n>>s;
  int a=0;
  for(int i=0;i<n;++i){
    int t=0;
    for(int j=0;j<n-i;++j){
      t=(t+1)*(s[j]==s[j+i]);
      a=max(a,min(t,i));
    }
  }
  cout<<a;
}""")
call(('g++','e.cpp'))
call('./a.out')
### BUGGY CODE ###

n,m = map(int,input().split())
a_list = []
c = []

for i in range(m):
    a,b = map(int,input().split())
    a_list += [a]
    c += [sum(1 << j-1 for j in list(map(int,input().split())))]

inf = 10**10
dp = [inf]*(1 << n)
dp[0] = 0

for i in range(1 << n):
    for j in range(m):
        dp[c[j]|i] = min(dp[c[j]|i],dp[i]+a_list[j])

if dp[-1] == inf:
    print(-1)
else:
    print(dp[-1])

### FIXED CODE ###

n,m = map(int,input().split())
a_list = []
c = []

for i in range(m):
    a,b = map(int,input().split())
    a_list.append(a)
    c.append(sum(1 << j-1 for j in list(map(int,input().split()))))

inf = 10**10
dp = [inf]*(1 << n)
dp[0] = 0

for i in range(1 << n):
    for j in range(m):
        dp[c[j]|i] = min(dp[c[j]|i],dp[i]+a_list[j])

if dp[-1] == inf:
    print(-1)
else:
    print(dp[-1])
### BUGGY CODE ###

from collections import defaultdict
n, m = map(int, input().split())
Gr = defaultdict(int)
for i in range(m):
    l, r, d = map(int, input().split())
    Gr[(l - 1, r - 1)] = d
    Gr[(r - 1, l - 1)] = -d


rec = True
for i in range(n):
    for j in range(n):
        for k in range(n):
            if (i, j) in Gr and (i, k) in Gr and (k, j) in Gr:
                if Gr[(i, j)] != Gr[(i, k)] + Gr[(k, j)]:
                    rec = False

if rec:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

import sys
sys.setrecursionlimit(200002)
N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    l, r, q = map(int, input().split())
    G[l - 1].append((r - 1, q))
    G[r - 1].append((l - 1, -q))
X = [None] * N


def dfs(u):
    global X, G
    for w, d in G[u]:
        if X[w] is None:
            X[w] = X[u] + d
            if not dfs(w):
                return False
        else:
            if X[w] != X[u] + d:
                return False

    return True


flag = True
for i in range(N):
    if X[i] is None:
        X[i] = 0
        flag &= dfs(i)

if flag:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC129 D

H,W = list(map(int,input().split()))
L = [list(input()) for _ in range(H)]
field = [[True for _ in range(W)] for _ in range(H)]

for i in range(H):
    for j in range(W):
        if L[i][j] == '#':
            field[i][j] = False

A = []

for i in range(H):
    for j in range(W):
        if field[i][j]:
            ans = 1
            for k in range(1,H):
                if i + k < H:
                    if field[i+k][j]:
                        ans += 1
                    else:
                        break
                else:
                    break
            for k in range(1,H):
                if i - k >= 0:
                    if field[i-k][j]:
                        ans += 1
                    else:
                        break
                else:
                    break
            for k in range(1,W):
                if j + k < W:
                    if field[i][j+k]:
                        ans += 1
                    else:
                        break
                else:
                    break
            for k in range(1,W):
                if j - k >= 0:
                    if field[i][j-k]:
                        ans += 1
                    else:
                        break
                else:
                    break
            A.append(ans)
print(max(A))


### FIXED CODE ###

#!/usr/bin/env python3
#ABC129 D

H,W = list(map(int,input().split()))
Lamp = [list(input()) for _ in range(H)]
field = [[True for _ in range(W)] for _ in range(H)]

for i in range(H):
    for j in range(W):
            if Lamp[i][j] == '#':
                field[i][j] = False
L = [[1 for _ in range(W)] for _ in range(H)]
R = [[1 for _ in range(W)] for _ in range(H)]
U = [[1 for _ in range(W)] for _ in range(H)]
D = [[1 for _ in range(W)] for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if field[i][j]:
            if i-1 >= 0:
                if field[i-1][j]:
                    D[i][j] = D[i-1][j]+1
            if j-1 >= 0:
                if field[i][j-1]:
                    L[i][j] = L[i][j-1]+1
for i in range(H)[::-1]:
    for j in range(W)[::-1]:
        if field[i][j]:
            if i+1 < H:
                if field[i+1][j]:
                    U[i][j] = U[i+1][j]+1
            if j+1 < W:
                if field[i][j+1]:
                    R[i][j] = R[i][j+1]+1

for i in range(H):
    for j in range(W):
        ans = max(ans,R[i][j]+L[i][j]+U[i][j]+D[i][j]-3)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
S = [sorted(input()[:-1]) for _ in [0]*N]

cnt = 0
for i, s in enumerate(S):
    for j, t in enumerate(S[i+1:]):
        if s == t:
            cnt += 1
print(cnt)

### FIXED CODE ###

N, *S = open(0).read().split()
S = [str(sorted(s)) for s in S]
D = {}
ans = 0
for s in S:
    if s in D:
        ans += D[s]
        D[s] += 1
    else:
        D[s] = 1
print(ans)
### BUGGY CODE ###

N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[0]*(N-1)
d=[[] for _ in range(N)]
e=[ set() for _ in range(N)] #存在する色のリスト
maxi=0
for i in range(N-1):
    a[i],b[i] = map(int,input().split())
    d[a[i]-1].append(b[i]-1)
    d[b[i]-1].append(a[i]-1)
for j in d:
    maxi=max(maxi,len(j))
for i in range(N-1):
    col=1
    while col in e[a[i]-1] or col in e[b[i]-1]:
        col +=1
        if col==maxi+1:
            col=1
    c[i]=col
    e[a[i]-1].add(col)
    e[b[i]-1].add(col)
   
print(maxi)
for color in c:
    print(color)

### FIXED CODE ###

from collections import deque

N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[set() for _ in range(N)] # 使用している色
d=[set() for _ in range(N)] # 隣接リスト
e=[ False for _ in range(N)] #訪問ずみかどうか
f=[0]*N  #答え
for i in range(N-1):
    a[i],b[i] = map(int,input().split())
    d[a[i]-1].add(b[i]-1)
    d[b[i]-1].add(a[i]-1)

maxi=max([len(d[i]) for i in range(N-1)])
print(maxi)
#print("c:",c)
#print("d",d)
#print("e",e)

#x=0としてBFSする

v=deque([0])
e[0]=True
color=1

while v:
  p = v.popleft()
  for q in d[p]:
    if e[q]==False:
      while color in c[p]:
        color +=1
        if color>maxi:
          color=1
      c[p].add(color)
      c[q].add(color)
      f[q]=color
      e[q]=True
      v.append(q)
      
for i in range(N-1):
  print( f[b[i]-1])
### BUGGY CODE ###

import collections

s = input()
s_len = len(s)
n = 2019
mod_list = [0]

for i in range(s_len):
    t = s[i:]
    t_i = int(t)
    m = t_i % n
    mod_list.append(m)

c = collections.Counter(mod_list)
result = sum(i * (i - 1) // 2 for i in c.values())
print(result)

### FIXED CODE ###

s = input()
s_len = len(s)
n = 2019
mod_list = [0] * n
mod_list[0] = 1

p = 1
d = 0
for t in reversed(s):
    d += int(t) * p
    m = d % n
    mod_list[m] += 1
    p *= 10
    p %= 2019

result = sum(i * (i - 1) // 2 for i in mod_list)
print(result)
### BUGGY CODE ###

import sys
from functools import reduce
sys.setrecursionlimit(10**6)


def main():

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

    def lcm_base(x, y):
        return (x * y) // gcd(x, y)

    def lcm(*numbers):
        return reduce(lcm_base, numbers, 1)

    n, m = map(int, input().split())
    a = list(map(int, input().split()))

    a0 = a[0]
    p = 0
    while a0 % 2 == 0:
        a0 //= 2
        p += 1
    elm = 2**p

    for ai in a:
        if (ai/elm) % 2 != 1:
            print(0)
            return

    lcm = lcm(*a)
    ans = (2*m+lcm) // (lcm*2)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from functools import reduce
sys.setrecursionlimit(10**6)


def main():

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

    def lcm_base(x, y):
        return (x * y) // gcd(x, y)

    def lcm(*numbers):
        return reduce(lcm_base, numbers, 1)

    n, m = map(int, input().split())
    a = list(map(int, input().split()))

    a0 = a[0]
    p = 0
    while a0 % 2 == 0:
        a0 //= 2
        p += 1
    elm = 2**p

    for ai in a:
        if (ai/elm) % 2 != 1:
            print(0)
            return

    lcm = lcm(*a)
    ans = (2*m+lcm) // (lcm*2)
    print(ans)


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

from collections import defaultdict

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

A=defaultdict(list)
Q=[]

for i in range(M):
  P,Y=map(int,input().split())
  Q.append([P,Y])
  A[P].append(Y)
  
for a,b in A.items():
  A[a].sort()

for l in Q:
  s=str(l[0]).zfill(6)
  num=A[l[0]].index(l[1])
  s+=str(num+1).zfill(6)
  print(s)

### FIXED CODE ###

from collections import defaultdict

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

Q=[]

for i in range(M):
  P,Y=map(int,input().split())
  Q.append([P,Y,i])
  
Q = sorted(Q,key=lambda x:x[1])
Q = sorted(Q,key=lambda x:x[0])

nowP=Q[0][0]
nownum=0

for l in Q:
  s=str(l[0]).zfill(6)
  if l[0]==nowP:
    nownum+=1
  else:
    nowP=l[0]
    nownum=1
  s+=str(nownum).zfill(6)
  l.append(s)
  
Q = sorted(Q,key=lambda x:x[2])

for l in Q:
  print(l[3])
### BUGGY CODE ###

import numpy as np

n,q=map(int,input().split())
s=str(input())

line = np.ones([n,])
for i in range(n-1):
    if (s[i:i+2]=="AC"): 
        line[i]=1
    else:
        line[i]=0
        

for i in range(q):
    l,r = map(int,input().split())
    target = line[l-1:r-1]
    print(int(sum(target)))

### FIXED CODE ###

import numpy as np

n,q=map(int,input().split())
s=str(input())

line = np.zeros([n,])
count = 0
for i in range(1,n):
    if (s[i-1:i+1]=="AC"): 
        count += 1
    line[i]=count 
        
for i in range(q):
    l,r = map(int,input().split())
    target = line[r-1] - line[l-1]
    print(int(target))
### BUGGY CODE ###

from sys import stdin

h,n = [int(x) for x in stdin.readline().rstrip().split()]
a = [0]*n ;b = [0]*n

for i in range(n):
    a[i],b[i] = [int(x) for x in stdin.readline().rstrip().split()]

#最高で削られる可能性がある体力
H = max(a)

inf = 10**10

#体力をちょうどi削るために必要な最低の魔力
dp = [inf for _ in range(h+H+1)];dp[0] = 0

for i in range(n):
    for j in range(h+1):
        if dp[j+a[i]] > dp[j] + b[i]:
            dp[j+a[i]] = dp[j] + b[i]

print(min(dp[h:]))

### FIXED CODE ###

from sys import stdin

h,n = [int(x) for x in stdin.readline().rstrip().split()]
a = [0]*n
b = [0]*n

for i in range(n):
    a[i],b[i] = [int(x) for x in stdin.readline().rstrip().split()]

#最高で削られる可能性がある体力
H = max(a)

inf = 10**10

#体力をちょうどi削るために必要な最低の魔力
dp = [inf for _ in range(h+H+1)]
dp[0] = 0

for i in range(n):
    for j in range(h+1):
        if dp[j+a[i]] > dp[j] + b[i]:
            dp[j+a[i]] = dp[j] + b[i]

print(min(dp[h:]))
### BUGGY CODE ###

N,Q = map(int,input().split()) 
S = list(input()) 
count = 0 
ans = [] 
for i in range(Q): 
  r,l = map(int,input().split()) 
  for k in range(r-1,l-1): 
     if S[k] == 'A' and S[k+1] == 'C': 
        count += 1 
  ans.append(count) 
  count = 0 
for j in range(len(ans)): 
  print(ans[j])                    

### FIXED CODE ###

N,Q = map(int,input().split())
S = list(input())
R = [0]*N
ans = []
temp = 0
for i in range(1,N):
  if S[i-1] == 'A' and S[i] == 'C':
    temp += 1
  R[i] = temp
for k in range(Q):
  l,r = map(int,input().split())
  ans.append(R[r-1]-R[l-1])
for j in range(len(ans)):
  print(ans[j])