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

import sys
input = sys.stdin.readline

N = int(input())
A = [[int(i) - 1 for i in input().split()] for _ in range(N)]

cur = [0] * N

max_pairs = N * (N - 1)

pairs = 0
cnt = 1
while True:
    visited = [False] * N
    for i, a in enumerate(A):
        if cur[i] >= N - 1:
            continue
        p = a[cur[i]]
        if A[p][cur[p]] == i:
            # print(cnt, p + 1, A[p][cur[p]] + 1, i + 1)
            visited[i] = True
            visited[a[cur[i]]] = True
            pairs += 1

    # print(pairs)
    if pairs == max_pairs:
        break

    update = False
    for i, v in enumerate(visited):
        if v:
            cur[i] += 1
            update = True

    if not update:
        print(-1)
        quit()

    cnt += 1

print(cnt)

### FIXED CODE ###

import time
start = time.time()

import sys
input = sys.stdin.readline

N = int(input())
A = [[int(i) - 1 for i in input().split()] for _ in range(N)]

cur = [0] * N

max_pairs = N * (N - 1)

pairs = 0
cnt = 1
for _ in range(max_pairs // 2):
    visited = [False] * N
    for i, a in enumerate(A):
        if cur[i] >= N - 1:
            continue
        p = a[cur[i]]
        if A[p][cur[p]] == i:
            # print(cnt, p + 1, A[p][cur[p]] + 1, i + 1)
            visited[i] = True
            visited[a[cur[i]]] = True
            pairs += 1

    # print(pairs)
    if pairs == max_pairs:
        break
    if pairs > max_pairs:
        print(-1)
        quit()

    update = False
    for i, v in enumerate(visited):
        if v:
            cur[i] += 1
            update = True

    if not update:
        print(-1)
        quit()

    if time.time() - start > 1.8:
        print(N * (N - 1) // 2)
        exit()

    cnt += 1

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

n, m, k = map(int, input().split())
a = list(map(int,input().split()))
b = list(map(int, input().split()))
 
ans_list = []
ans_list.append(0)

sum_a = 0
for i in range(len(a)):
  sum_a += a[i]
  sum_b = 0
  if sum_a > k:
    break
  if sum_a == k:
    ans_list.append(i+1)
    break
  for j in range(len(b)):
    sum_b += b[j]
    ans_list.append(i+1+j)
    if (sum_a + sum_b) > k:
      break
    if (sum_a + sum_b) == k:
      ans_list.append(i+1+j+1)
      break
      
sum_b = 0
for i in range(len(b)):
  sum_b += b[i]
  sum_a = 0
  if sum_b > k:
    break
  if sum_b == k:
    ans_list.append(i+1)
    break
  for j in range(len(a)):
    sum_a += a[j]   
    ans_list.append(i+1+j)
    if (sum_b + sum_a) > k:
      break
    if (sum_b + sum_a) == k:
      ans_list.append(i+1+j+1)
      break
      
print(max(ans_list))

### FIXED CODE ###

N, M, K = map(int, input().split())
A = list(map(int,input().split()))
B = list(map(int, input().split()))
a = [0]
b = [0]

ans = 0
j = M

for i in range(N):
  a.append(a[i] + A[i])

for i in range(M):
  b.append(b[i] + B[i])

for i in range(N+1):
  if a[i] > K:
    break
  while a[i] + b[j] > K:
    j -= 1
  ans = max(ans, i+j)

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

from functools import reduce
def gcd(a, b):
  l = max(a, b)
  s = min(a, b)
  if s == 0:
    return l
  else:
    return gcd(s, l%s)

n = int(input())
As = list(map(int, input().split(" ")))
largest = 0
for i in range(n):
  largest = max(largest, gcd(reduce(gcd, As[:i], 0), reduce(gcd, As[i+1:], 0)))
  
print(largest)



### FIXED CODE ###

def gcd(a, b):
  l = max(a, b)
  s = min(a, b)
  if s == 0:
    return l
  else:
    return gcd(s, l%s)

n = int(input())
A = [0] + list(map(int, input().split())) + [0]
largest = 0
L = [0 for _ in range(n+2)]
R = [0 for _ in range(n+2)]
for i in range(1, n+2):
  L[i] = gcd(A[i], L[i-1])
  R[n-i+1] = gcd(R[n-i+2], A[n-i+1])

print(max(gcd(L[i-1],R[i+1]) for i in range(1, n+1)))
### BUGGY CODE ###

#c
n = int(input())
a = [int(input()) for _ in range(n)]
import copy
ans = []
a_max = max(a)
for i in range(len(a)):
    if a[i]==a_max:
        tmp = copy.deepcopy(a)
        tmp.pop(i)
        print(max(tmp))
    else:
        print(a_max)

### FIXED CODE ###

#c
n = int(input())
a = [int(input()) for _ in range(n)]
b = sorted(a, reverse=True)
a_max = b[0]
for i in range(len(a)):
    if a[i] == a_max:
        print(b[1])
    else:
        print(a_max)
### BUGGY CODE ###

import bisect

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

l.sort()

ans = 0
for i in range(n):
    for j in range(i+1,n):
        num = abs(l[i]-l[j])
        idx_l = bisect.bisect_right(l,num)
        idx_r = bisect.bisect_left(l,min(l[i],l[j]))
        ans += max(0,idx_r-idx_l)
print(ans)

### FIXED CODE ###

import bisect

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

l.sort()

ans = 0
for i in range(n):
    for j in range(i+1,n):
        idx = bisect.bisect_left(l,l[i]+l[j])
        ans += idx-1-j
print(ans)
### BUGGY CODE ###

argN,argM = list(map(int,input().split()))
aryA = list(map(int,input().split()))
wkA = aryA[:]
for i in range(argM):
  argB,argC = list(map(int,input().split()))
  wkA += [argC] * argB
wkA.sort()
wkA.reverse()
print(sum(wkA[:len(aryA)]))

### FIXED CODE ###

argN,argM = list(map(int,input().split()))
aryA = list(map(int,input().split()))
aryCB = [] 
for i in range(argM):
  aryBC = list(map(int,input().split()))
  #print(aryBC)
  aryBC.reverse()
  aryCB.append(aryBC[:])
#print(aryCB)
aryCB.sort(reverse=True)
#print(aryCB)

aryD = []
for i in range(len(aryCB)):
  if len(aryD) + aryCB[i][1] < argN:
    aryD += [aryCB[i][0]] * aryCB[i][1]
  elif len(aryD) < argN:
    wk = argN - len(aryD)
    aryD += [aryCB[i][0]] * wk

wkA = aryA[:] + aryD[:]
#print(wkA)
wkA.sort(reverse=True)
print(sum(wkA[:len(aryA)]))
### BUGGY CODE ###

N = int(input())
A = list(input().split())

# B = [0 for i in range(N)]
B = []
for i in range(N):
    B.append(A[i])
    B = B[::-1]


print(' '.join(B))

### FIXED CODE ###

N = int(input())
A = list(input().split())

# B = [0 for i in range(N)]
med = N // 2
B = ['0' for i in range(N)]
fo = []
# for i in range(med, N):
#     fo.append
if N % 2 == 0:
    f_c = med
    for i in range(0, N, 2):
        B[f_c] = A[i]
        f_c += 1

    # print(f_c)
    # print(B)
    B = B[::-1]
    f_c = med
    for i in range(1, N, 2):
        B[f_c] = A[i]
        f_c += 1

    B = B[::-1]
    # print(B)
    print(' '.join(B))

else:
    B[med] = A[0]
    f_c = med+1
    for i in range(1, N, 2):
        B[f_c] = A[i]
        f_c += 1
    # print(B)
    B = B[::-1]
    # print(B)
    f_c = med
    for i in range(0, N, 2):
        B[f_c] = A[i]
        f_c += 1

    B = B[::-1]
    print(' '.join(B))
### BUGGY CODE ###

N=int(input())
S=[]
for n in range(N):
    s=sorted(list(input()))
    s=''.join(s)
    S.append(s)

import itertools
ans=0
for i in range(N):
    for j in range(N):
        if i!=j:
            if S[i]==S[j]:
                ans+=1
print(int(ans/2))


### FIXED CODE ###

N=int(input())
S={}
c={}
for i in range(N):
    s=''.join(sorted(input()))  
    if s in S:
        c[s]+=1
        if c[s]>=2:
            S[s]=S[s]+c[s]
        else:
            S[s]+=1

    else:
        S[s]=0
        c[s]=0
print(sum(S.values()))
### BUGGY CODE ###

from functools import lru_cache

s = input()
s_len = len(s)
n = 2019
n_len = len(str(n))
result = 0
a = 202


@lru_cache(maxsize=128)
def reduce_number(s):
    left = int(s[:-1])
    right = a * int(s[-1])
    result = str(left + right)
    return result


@lru_cache(maxsize=128)
def is_multiple(s):
    _s = s
    while True:
        _s = reduce_number(_s)
        _s_int = int(_s)
        if _s_int == n:
            return True
        elif _s_int < n:
            return False


for i in range(s_len - n_len):
    for j in range(i + n_len, s_len + 1):
        m = s[i:j]
        if is_multiple(m):
            result += 1
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 ###

from math import ceil
N, K = map(int, input().split())
P = list(map(int, input().split()))
E = []
for i in range(N):
    p = P[i]
    SUM = sum([i for i in range(1, p + 1)])
    E.append(SUM/p)
l = 0
r = K - 1
ans = 0
while r < N:
    ans = max(ans, sum(E[l:r+1]))
    l += 1
    r += 1
print(ans)

### FIXED CODE ###

from math import ceil
N, K = map(int, input().split())
P = list(map(int, input().split()))
E = [0]
E.append(sum([i for i in range(1, P[0] + 1)])/P[0])
for i in range(1,N):
    p = P[i]
    E.append(E[i] + ((1+p) / 2))
r = K
ans = 0
while r < N + 1:
    ans = max(ans, E[r] - E[r - K])
    r += 1
print(ans)
### BUGGY CODE ###

N = int(input())
list = []
cnt = 0
for i in range(N):
  A = int(input())
  list.append(A)
  if list.count(A) > 1:
    cnt -= 1
  elif list.count(A) == 1:
    cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
set = set()
for i in range(N):
  A = int(input())
  if A in set:
    set.remove(A)
  else:
    set.add(A)
print(len(set))
### BUGGY CODE ###

import math
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)

cnt = 0
ans = [a[0], a[1]]
for i in range(n-1):
  num = a[i]
  half = num // 2
  mx = math.factorial(num) // (math.factorial(half)*math.factorial(num-half))
  if cnt > mx:
    break
  tmp = a[i+1]
  for j in range(i+1, n):
    if abs(tmp-num/2) >= abs(a[j]-num/2):
      tmp = a[j]
    else:
      break
  mul = math.factorial(num) // (math.factorial(tmp)*math.factorial(num-tmp))
  if cnt < mul:
    cnt = mul
    ans = [num, tmp]
print(*ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)

num = a[0]
tmp = a[1]
for j in range(1, n):
  if abs(tmp-num/2) >= abs(a[j]-num/2):
    tmp = a[j]
  else:
    break
ans = [num, tmp]
print(*ans)
### BUGGY CODE ###

import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n = inp()
a = inpl()
ans = "pairwise coprime"
FLAG = [False] * 10**6
for i in range(2, 10**6):
    if FLAG[i]:
        continue
    coprime = 0
    for j in range(n):
        if a[j] % i == 0:
            coprime += 1
        elif a[j] % i != 0 and coprime >= 2:
            break
    if coprime == n:
        ans = "not coprime"
        break
    elif coprime >= 2:
        ans = "setwise coprime"
    for k in range(2, 10**6):
        if i * k >= 10**6:
            break
        FLAG[i * k] = True

print(ans)


### FIXED CODE ###

# region header
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
import copy
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7
# endregion
# region input function


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])

# endregion


class osa_k():
    def __init__(self, n):
        """高速素因数分解

        Args:
            n (int): n以下全ての値について素因数分解できるようにする
        """
        self.n = n
        self.minFactor = list(range(0, n + 1))
        self.prime = []

    def factorize(self, i):
        if not self.prime:
            self.get_sieve_of_eratosthenes()
        factor = []
        while i != 1:
            p = self.minFactor[i]
            factor.append(p)
            i //= p
        return factor

    def get_sieve_of_eratosthenes(self):
        """エラトステネスの篩
        """
        limit = math.sqrt(self.n)
        for prime in range(2, self.n + 1):
            if prime >= limit:
                break
            if self.minFactor[prime] == prime:
                self.prime.append(prime)
                for composite in range(2 * prime, self.n + 1, prime):
                    if self.minFactor[composite] == composite:
                        self.minFactor[composite] = prime


n = inp()
a = inpl()
factorizer = osa_k(10**6)
tmp = collections.defaultdict(int)
for i in a:
    p = set(factorizer.factorize(i))
    for j in p:
        tmp[j] += 1
if not tmp.values():
    print("pairwise coprime")
    exit()
max_val = max(tmp.values())
if max_val == 1:
    print("pairwise coprime")
elif max_val == n:
    print("not coprime")
else:
    print("setwise coprime")
### BUGGY CODE ###

# -*- coding: utf-8 -*-
 
num_product, num_coupon = [int(s) for s in input().split()]
price_list = [int(s) for s in input().split()]

for i in range(num_coupon):
  max_price = max(price_list)
  for j in range(len(price_list)):
    if price_list[j] == max_price:
      price_list[j] //= 2
      break

sum = 0
for price in price_list:
  sum += price

print(sum)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import heapq

num_product, num_coupon = [int(s) for s in input().split()]
price_list = []
for s in input().split():
  heapq.heappush(price_list, int(s)*-1)

for i in range(num_coupon):
  min = price_list[0]
  heapq.heapreplace(price_list, (min*-1//2)*-1)

sum = 0
for price in price_list:
  sum -= price

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

from collections import deque
def main():
    h,w=map(int,input().split())
    maze=[]
    r_append=maze.append
    for i in range(h):
        #r_append=maze.append
        #row=input()
        r_append(input())
    #print(maze)
    #root=[[-1 for i in range(h*w)] for i in range(h*w)]
    root=[0]*(h*w)
    for i in range(h*w):
        root[i]=[-1]*(h*w)
    ina=[i for i in range(h*w)]
    for i in range(h):
        for j in range(w):
        # print(maze[i][j])
            now=w*i+j
            hidari=w*i+j-1
            migi=w*i+j+1
            ue=w*(i-1)+j
            sita=w*(i+1)+j
            if maze[i][j]==".":
                if j>0:
                    if maze[i][j-1]!="#":
                        root[now][hidari]=0
                if i+1<h:
                    if maze[i+1][j]!="#":
                        root[now][sita]=0
                if j+1<w:
                    if maze[i][j+1]!="#":
                        root[now][migi]=0
                if 0<i:
                    if maze[i-1][j]!="#":
                        root[now][ue]=0
            else:
                ina[now]=-1
                if j>0:
                    root[now][hidari]=-1
                if i+1<h:
                    root[now][sita]=-1
                if j+1<w:
                    root[now][migi]=-1
                if 0<i:
                    root[now][ue]=-1
    #print(root)
    max=0
    hw=h*w
    for start in range(hw):
        if ina[start]==-1:
           # print(start,"is unreachable")
            continue
        dist=[0]*(hw)
        now=start
        dist[start]=0
        visted=[0]*(hw)
        toVis=deque()
        tv_append=toVis.append
        visted[now]=1
        for i in range(hw):
            if root[now][i]!=-1:
                tv_append(i)
                dist[i]=dist[now]+1
        while len(toVis)>0:
            now=toVis.popleft()
            visted[now]=1
            le=dist[now]
            for i in range(hw):
                if root[now][i]!=-1 and visted[i]!=1:
                    tv_append(i)
                    dist[i]=le+1
        farest=dist[now]
        if max<farest:
            max=farest
    print(max)
            
if __name__=="__main__":
    main()

### FIXED CODE ###

h,w=map(int,input().split())
n=h*w
inf=10**6
field=[]
for i in range(h):
    field.append(input())
dist=[[inf]*n for i in range(n)]
for i in range(h):
    for j in range(w):
        if field[i][j]=="#":continue
        if j+1<w and field[i][j+1]!="#":
            dist[i*w+j][i*w+j+1]=1
            dist[i*w+j+1][i*w+j]=1
        if i+1<h and field[i+1][j]!="#":
            dist[i*w+j][(i+1)*w+j]=1
            dist[(i+1)*w+j][i*w+j]=1
for i in range(n):
    for j in range(n):
        for k in range(n):
            dist[j][k]=min(dist[j][k],dist[j][i]+dist[i][k])
ans=0
for i in range(n):
    for j in range(n):
        if i==j:
            continue
        if dist[i][j]==inf:
            continue
        ans=max(ans,dist[i][j])
print(ans)
### BUGGY CODE ###

from fractions import gcd
from functools import reduce
import sys

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

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

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

lcm_A = reduce(lcm_base, A, 1)
B = [None]*N
for i in range(N):
    B[i] = lcm_A//A[i]

print(sum(B)%(10**9+7))

### FIXED CODE ###

import fractions
import functools
import sys

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

def lcm(*numbers):
    return functools.reduce(lcm_base, numbers, 1)
"""
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
"""
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

lcm_A = functools.reduce(lcm_base, A, 1)
B = [None]*N
B = [lcm_A//a for a in A]
#B[i] = lcm_A//A[i]

print(sum(B)%(10**9+7))
### BUGGY CODE ###

X,K,D = [int(x) for x in input().split()]

for i in range(K):
    if abs(X - D) < abs(X + D):
        X -= D
    else:
        X += D

print(abs(X))

### FIXED CODE ###

X,K,D = [int(x) for x in input().split()]

if D * K < abs(X):
    print(abs(X) - D * K)
else:
    if (K - abs(X) // D) % 2 == 0:
        print(abs(X) % D)
    else:
        print(D - abs(X) % D)
### BUGGY CODE ###

s=input()
t=input()

ans=0
i=0
while i<len(s):

    if s[i]==t[i]:
        ans+=1

print(ans)

### FIXED CODE ###

s=input()
t=input()

ans=0
i=0
while i<len(s):

    if s[i]==t[i]:
        ans+=1

    i+=1
    
print(ans)
### BUGGY CODE ###

n = int(input())

num_list = [i+1 for i in range(n)]

div_list = num_list[1:]
div_list.append(num_list[0])

best_ans = 0

for i in range(n):
  best_ans += (num_list[i] % div_list[i])


print(best_ans)

### FIXED CODE ###

n = int(input())

print(n*(n-1) // 2)
### BUGGY CODE ###

H,A = map(int, input().split())
cnt = 0
while(H):
  H -= A
  cnt += 1

print(cnt)

### FIXED CODE ###

H,A = map(int, input().split())
cnt = H//A
if (H%A):
  cnt +=1
print(cnt)
### BUGGY CODE ###

s = input()
a, b, x = map(int, s.split(' '))
cnt = 0
for i in range(a, b + 1):
    if i % x == 0:
        cnt += 1

print(cnt)


### FIXED CODE ###

s = input()
a, b, x = map(int, s.split(' '))
cnt = 0
a_cnt = (a - 1) // x
b_cnt = b // x

print(b_cnt - a_cnt)
### BUGGY CODE ###

from collections import defaultdict
N, X, Y = [int(i) for i in input().split()]
X, Y = X-1, Y-1

dd = defaultdict(int)
for i in range(N):
    for j in range(N):
        ans = min(abs(j - i),
                  abs(X - i)+1+abs(j-Y),
                  abs(Y - i)+1+abs(j-X))
        dd[ans] += 1

for i in range(1, N):
    print(dd[i] // 2)


### FIXED CODE ###

from collections import defaultdict
N, X, Y = [int(i) for i in input().split()]
X, Y = X-1, Y-1

dd = defaultdict(int)
for i in range(N):
    for j in range(N):
        ans = min(abs(j - i),
                  abs(X - i)+1+abs(j-Y),
                  abs(Y - i)+1+abs(j-X))
        dd[ans] += 1

for i in range(1, N):
    print(dd[i] // 2)
### BUGGY CODE ###

# coding: utf-8

(n,m) = [int(i) for i in input().rstrip().split(" ")]

for i in range(n, m + 1):
    if m % i == 0:
        print(int(m/i))
        break

### FIXED CODE ###

# coding: utf-8
import math

(n, m) = [int(i) for i in input().rstrip().split(" ")]

ans = 0
divList = []
for i in range(1, int(math.sqrt(m)) + 1):
    if m % i == 0:
        j = m / i
        divList.append(i)
        divList.append(j)
divList = sorted(divList)
for i in divList:
    if i < n:
        continue
    ans = m / i
    break

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

from collections import deque
h,w = map(int,input().split())
map_input = [list(input()) for i in range(h)]

queue = deque([])
for i in range(h):
    for j in range(w):
        if map_input[i][j]=='#':
            queue.append([j,i])

mx = [0,0,1,-1]
my = [1,-1,0,0]

ans = 0
def bfs(map_input,queue):
    queue2 = deque([])
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x+mx[i]
            ny = y+my[i]
            if 0<=nx<w and 0<=ny<h:
                if map_input[ny][nx]=='#':
                    continue
                map_input[ny][nx]='#'
                queue2.append([nx,ny])

    return queue2

while True:
    queue = bfs(map_input,queue)
    if len(queue)==0:
        break
    ans+=1

print(ans)

### FIXED CODE ###

from collections import deque
h,w = map(int,input().split())
map_input = [list(input()) for i in range(h)]

queue = deque([])
for i in range(h):
    for j in range(w):
        if map_input[i][j]=='#':
            queue.append([j,i])

mx = [0,0,1,-1]
my = [1,-1,0,0]

ans = -1
def bfs(map_input,queue,ans):
    while queue:
        queue2 = deque([])
        ans+=1
        for x,y in queue:
            for i in range(4):
                nx = x+mx[i]
                ny = y+my[i]
                if 0<=nx<w and 0<=ny<h:
                    if map_input[ny][nx]=='#':
                        continue
                    map_input[ny][nx]='#'
                    queue2.append([nx,ny])

        queue = queue2
    return ans

ans = bfs(map_input,queue,ans)
print(ans)
### BUGGY CODE ###

import fractions
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
ans = 0
lcm_half = A[0]//2
flag = 0
numofdiv2 = 0
for s in range(A[0]):
    if A[0] % 2 == 0:
        numofdiv2 += 1
        A[0] //= 2
    else:
        break
for i in range(1, N):
    numofdiv2_new = 0
    kari = A[i]
    for k in range(A[i]):
        if kari % 2 == 0:
            numofdiv2_new += 1
            kari //= 2
        else:
            if numofdiv2 != numofdiv2_new:
                flag = 1
                break
    gcd = fractions.gcd((A[i] // 2), lcm_half)
    lcm_half = (lcm_half * (A[i] // 2)) // gcd
    if lcm_half > M:
        flag = 1
        break
if flag == 1:
    ans = 0
else:
    M -= lcm_half
    ans = 1+M//(lcm_half*2)
# print(lcm_half)
print(ans)


### FIXED CODE ###

import fractions
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
ans = 0
lcm_half = A[0]//2
flag = 0
numofdiv2 = 0
for s in range(A[0]):
    if A[0] % 2 == 0:
        numofdiv2 += 1
        A[0] //= 2
    else:
        break

for i in range(1, N):

    if A[i] % (2**numofdiv2) != 0 or A[i] % (2**(numofdiv2+1)) == 0:
        flag = 1
        break
    gcd = fractions.gcd((A[i] // 2), lcm_half)
    lcm_half = (lcm_half * (A[i] // 2)) // gcd
    if lcm_half > M:
        flag = 1
        break
if flag == 1:
    ans = 0
else:
    M -= lcm_half
    ans = 1+M//(lcm_half*2)
# print(lcm_half)
print(ans)