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

#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 2019
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

S = input()
N = len(S)

d = defaultdict(int)
d[0] += 1
cnt = 0
nums = [0]*(N+1)
for i in range(N):
    m = 10**(N-i-1)%MOD
    val = (int(S[i])*m + nums[i])%MOD
    nums[i+1] = val
    cnt += d[val]
    d[val] += 1
print(cnt)

### FIXED CODE ###

#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 2019
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

S = input()
N = len(S)

d = defaultdict(int)
d[0] += 1
# nums = [0]*(N+1)
m = 0
last = 0
dd = 1
for i in range(N):
    m += int(S[N-i-1])*dd
    m %= MOD
    # val = (int(S[i])*m + nums[i])%MOD
    # cnt += d[val]
    dd = (dd*10)%MOD
    d[m] += 1

cnt = 0
for i, v in d.items():
    cnt += v*(v-1)//2
print(cnt)
### BUGGY CODE ###

n = int(input())
count = 0
 
for i in range(1, n+1):
  for j in range(1, n+1):
    if str(i)[0] == str(j)[-1] and str(i)[-1] == str(j)[0]:
      count += 1
print(count)

### FIXED CODE ###

n = int(input())
d = {}

for i in range(1, n+1):
  start, end = str(i)[0], str(i)[-1]
  d[(start, end)] = d.get((start, end), 0) + 1
count = 0
for key, n_key in d.items():
  count += n_key * d.get(tuple(reversed(key)), 0)
print(count)
### BUGGY CODE ###

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


def gcd_list(lst):
    a = lst[0]
    for i in lst[1:]:
        a = gcd(a, i)
    return a


n = int(input())
a = list(map(int, input().split()))
max_value = max(a)
ans = 0
for i in range(n):
    target = a[:i]
    target.extend(a[i+1:])
    target.append(max_value)
    ans = max(ans, gcd_list(target))
print(ans)


### FIXED CODE ###

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


def gcd_list(lst):
    a = lst[0]
    for i in lst[1:]:
        a = gcd(a, i)
    return a


n = int(input())
a = list(map(int, input().split()))
l = [0 for _ in range(n)]
r = [0 for _ in range(n)]
for i in range(n-1):
    l_i = 0 if 0 == i else l[i]
    l[i+1] = gcd(l_i, a[i])
for i in range(n)[::-1]:
    r_i1 = 0 if i == n-1 else r[i+1]
    r[i] = gcd(r_i1, a[i])
m = []
for i in range(n):
    r_i1 = 0 if i == n-1 else r[i+1]
    m.append(gcd(l[i], r_i1))
print(max(m))
### BUGGY CODE ###

import sys
import itertools
from collections import deque
from operator import itemgetter

input = sys.stdin.readline
S = input()
counter = 0

for i in range(len(S)):
    if '01' in S:
        S = S.replace('01', '', 1)
        counter += 1
    if '10' in S:
        S = S.replace('10','', 1)
        counter += 1
print(2*counter)

### FIXED CODE ###

import sys
import itertools
from collections import deque
from operator import itemgetter

input = sys.stdin.readline
S = input()
counter = 0

A = S.count('1')
B = S.count('0')
print(2*min(A,B))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n, m = [int(item) for item in input().split()]
if m % 2 != 0:
    print(-1)
    exit()
vset = set()
edge = [[] for _ in range(n)]
for i in range(m):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)
 
ans = []
def dfs(prev, n):
    if prev < n:
        if (prev, n) in vset:
            return 0 
        else:
            vset.add((prev, n))
    else:
        if (n, prev) in vset:
            return 0 
        else:
            vset.add((n, prev))
    child_num = 0
    for v in edge[n]:
        if prev == v:
            continue
        if dfs(n, v) == 1:
            child_num += 1
            ans.append([n+1, v+1])
    if child_num % 2 == 0:
        return 1
    else:
        ans.append([n+1, prev+1])
        return 0
 
dfs(-1, max(0, n - 2))
print("\n".join([str(f) + " " + str(t) for f, t in ans]))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, m = [int(item) for item in input().split()]
if m % 2 != 0:
    print(-1)
    exit()
visited_e = [False] * m
visited_v = [False] * n
edge = [[] for _ in range(n)]
for i in range(m):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    edge[a].append([b, i])
    edge[b].append([a, i])
 
ans = []
def dfs(prev, n):
    if visited_v[n]:
        return 1
    visited_v[n] = True
    child_num = 0
    for v, index in edge[n]:
        if visited_e[index]:
            continue
        visited_e[index] = True
        if dfs(n, v) == 1:
            child_num += 1
            ans.append([n+1, v+1])
    if child_num % 2 == 0:
        return 1
    else:
        ans.append([n+1, prev+1])
        return 0
 
dfs(-1, 0)
print("\n".join([str(f) + " " + str(t) for f, t in ans]))
### BUGGY CODE ###

import math as m

Z = 10 ** 9 + 7

conb_table = {}
def conb(S, i):
    if (not (S in conb_table)):
        conb_table[S] = {}
    if (i in conb_table[S]):
        return conb_table[S][i]
    if (i == 1):
        v = 1
    elif (i == 2):
        v = S - 1
    elif (i == 3):
        v = (S - 1) * (S - 2) // 2
    else:
        v = 0
        for j in range(1, S - i + 2):
            v += conb(S - j, i - 1)
    conb_table[S][i] = v
    return v

def calc(N, K):
    M = N - K + 1
    M_fact = m.factorial(M)
    result = ''
    for i in range(1, K + 1):
        if (M - i < 0):
            val = 0
        else:
            val = m.factorial(M) // m.factorial(i) // m.factorial(M - i) * conb(K, i)
        result += "{}\n".format(
            val if val < Z else val % Z
            )
    print(result)

s = input().split(' ')
N = int(s[0])
K = int(s[1])

calc(N, K)

### FIXED CODE ###

import math as m

Z = 10 ** 9 + 7


def calc(N, K):
    M = N - K + 1
    M_fact = m.factorial(M)
    K1_fact = m.factorial(K - 1)
    result = ''
    for i in range(1, K + 1):
        if (M - i < 0):
            val = 0
        else:
            val = M_fact // m.factorial(i) // m.factorial(M - i) * \
                K1_fact // m.factorial(i - 1) // m.factorial(K - i)
        result += "{}\n".format(
            val if val < Z else val % Z
        )
    print(result)


s = input().split(' ')
N = int(s[0])
K = int(s[1])

calc(N, K)
### BUGGY CODE ###

def main():
    S=input()
    a=0 
    b=[0]*2019
    l=[0]*2019
    for i in S:
        k=int(i)
        for j in range(2019):
            l[(j*10+k)%2019]=b[j]
        l[k]+=1
        a+=l[0]
        b=l.copy()
    print(a)
main()


### FIXED CODE ###

S=input()
a=0
b=[0]*2019
No=[None]*2019
for i in S:
    l=No.copy()
    k=int(i)
    for j in range(2019):
        l[(j*10+k)%2019]=b[j]
    l[k]+=1
    a+=l[0]
    b=l
print(a)
### BUGGY CODE ###

import math
N, K = map(int, input().split())
As = sorted(list(map(int, input().split())))
Bs = sorted(list(map(int, input().split())))[::-1]
Cs = [a*b for a, b in zip(As, Bs)]
BCs = list(zip(Bs, Cs))

def func(target):
    r = 0
    for b, c in BCs:
        r += math.ceil(max(0, c - target) / b)
    return r <= K

if __name__ == '__main__':
    min_i, max_i, index = 0, max(Cs)+1, 1
    while True:
        if not func(index):
            if func(index+1):
                print(index+1)
                break
            index, min_i = (index+1 + max_i)//2, index+1
            continue
        index, max_i = (index-1 + min_i)//2, index-1


### FIXED CODE ###

import math
N, K = map(int, input().split())
As = sorted(list(map(int, input().split())))
Bs = sorted(list(map(int, input().split())))[::-1]
Cs = [a*b for a, b in zip(As, Bs)]
BCs = list(zip(Bs, Cs))

def func(target):
    r = 0
    for b, c in BCs:
        r += math.ceil(max(0, c - target) / b)
    return r <= K

if __name__ == '__main__':
    min_i, max_i, index = 0, max(Cs)+1, 1
    while True:
        if func(index):
            index, max_i = (index-1 + min_i)//2, index-1
        else:
            index, min_i = (index+1 + max_i)//2, index+1
        if min_i > max_i:
            print(min_i)
            break
### BUGGY CODE ###

import numpy as np

n, m = map(int, input().split())
A = list(map(int, input().split()))
C = []
for _ in range(m):
    b, c = map(int, input().split())
    C += [c]*b

A.sort()
C.sort(reverse=True)
threshold = np.count_nonzero((np.array(C[:len(A)]) - np.array(A[:len(C)])) > 0)

print(sum(C[:threshold]) + sum(A[threshold:]))

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(m)]

a.sort()
bc.sort(reverse=True, key=lambda x: x[1])
j = 0
for i in range(m):
    while j < len(a) and bc[i][0] > 0:
        if a[j] < bc[i][1]:
            a[j] = bc[i][1]
            bc[i][0] -= 1
        j += 1
print(sum(a))
### BUGGY CODE ###

A=input()
list1=input().split()
A=int(A)
Ans=1
for i in range(0,A):
    Ans= Ans*int(list1[i])
if 10**18<Ans:
    print(-1)
else:   
    print(Ans)    
        

### FIXED CODE ###

A=input()
list1=input().split()
A=int(A)
Ans=1
#---------------------------

if "0" in list1:
    print("0")
    
else:
    for i in range(0,A):
        Ans=Ans*int(list1[i])    
        if Ans >10**18:
                print(-1)
                break
    if Ans <=10**18:    
        print(Ans)
### BUGGY CODE ###

N = int(input())
for i in range(1, 3501):
    for j in range(1, 3501):
        tmp = 4 * i * j - N * j - N * i
        if tmp != 0 and (N * i * j) % tmp == 0:
            k = (N * i * j) // (4 * i * j - N * j - N * i)
            if k>0:
                print(i, j, k)
                exit()


### FIXED CODE ###

N = int(input())
for i in range(1, 3501):
    for j in range(1, 3501):
        tmp = 4 * i * j - N * j - N * i
        if tmp != 0 and (N * i * j) % tmp == 0:
            k = (N * i * j) // (4 * i * j - N * j - N * i)
            if k>0:
                print(i, j, k)
                exit()
### BUGGY CODE ###

import math

def primelis(n):
    a = []
    if n % 2 == 0:
        a.append(2)
        while n%2==0:
          n=n//2
    f = 3
    while f * f <= n:
      if n%f==0:
        a.append(f)
        while n%f==0:
          n=n//f
    if n != 1:
        a.append(n)
    return a



n=int(input())

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

gcd=A[0]

for i in range(n-1):
  gcd=math.gcd(gcd,A[i+1])

plis=[0 for i in range(10**6)]

if gcd!=1:
  print("not coprime")
else:
  check=0
  for i in range(n):
    for pi in primelis(A[i]):
      if plis[pi-1]!=0:
        check=1
        break
      else:
        plis[pi-1]+=1
    if check==1:
      break
  if check==1:
    print("setwise coprime")
  else:
    print("pairwise coprime")



### FIXED CODE ###

import math

def primelis(n):
    a = []
    if n % 2 == 0:
        a.append(2)
        while n%2==0:
          n=n//2
    f = 3
    while f * f <= n:
      if n%f==0:
        a.append(f)
        while n%f==0:
          n=n//f
    if n != 1:
        a.append(n)
    return a



n=int(input())

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

gcd=A[0]

for i in range(n-1):
  gcd=math.gcd(gcd,A[i+1])

d=[0 for i in range(10**6+1)]

for i in range(2,10**6+1):
  if d[i]==0:
    j=1
    while i*j<=10**6:
      d[i*j]=i
      j+=1

nglis=[0 for i in range(10**6+1)]

if gcd!=1:
  print("not coprime")
else:
  check=0
  for i in range(n):
    if nglis[A[i]]==1:
      check=1
      break
    else:
      ai=A[i]
      while ai!=1:
        j=1
        while d[ai]*j<=10**6:
          nglis[d[ai]*j]=1
          j+=1
        ai=ai//d[ai]
  if check==1:
    print("setwise coprime")
  else:
    print("pairwise coprime")
### BUGGY CODE ###

N=int(input())
ans = 0
for j in range(1,N+1):
  for i in range(1,N+1):
    if i % j == 0:
      ans += i
print(ans)

### FIXED CODE ###

N = int(input())

def cnt(n):
  c = 0
  for i in range(1, N+1):
    n = N // i
    j  = i * n
    c += (i + j) * n // 2
  return c

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

N = int(input())
L = [input() for i in range(N)]
L = list(map("".join, list(map(sorted, list(map(list, L))))))
count = 0
for j in range(N):
    for k in range(j + 1, N):
        if L[j] == L[k]:
            count = count + 1
print(count)

### FIXED CODE ###

import math
N = int(input())
L = [input() for i in range(N)]
L = sorted(list(map("".join, list(map(sorted, list(map(list, L)))))))
c = 0
ans = 0
for j in range(1,N):
    if not L[j] == L[j - 1]:
        ans += (j - c)*(j - c - 1)/2
        c = j
    elif j + 1 == N:
        ans += (j + 1 - c)*(j - c)/2
print(int(ans))
### BUGGY CODE ###

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

count=0
pin=[]*721
for p in range(N-2):
    for q in range(1,N-1):
        if p>=q:
            continue
        for r in range(2,N):
            if q>=r:
                continue
            n=int(S[p]+S[q]+S[r])
            if not n in pin:
                pin.append(n)
print(len(pin))


### FIXED CODE ###

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

count=0
for p in range(10):
    s=S.find(str(p))
    if s==-1:
        continue
    for q in range(10):
        t=S.find(str(q),s+1)
        if t==-1:
            continue
        for r in range(10):
            u=S.find(str(r),t+1)
            if u!=-1:
                count+=1
print(count)
### BUGGY CODE ###

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

dp = [[1 if _2 == 0 else 0 for _2 in range(s + 1)] for _1 in range(n+1)]

MOD = 998244353

for i, ai in enumerate(a):
  for j, v in enumerate(dp[i]):
    dp[i + 1][j] += v
    dp[i + 1][j] %= MOD 
    if j + ai <= s:
      dp[i + 1][j + ai] += v
      dp[i + 1][j + ai] %= MOD


print(sum(dp_i[s] for dp_i in dp) % MOD)
    

### FIXED CODE ###

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

dp = [[1 if _2 == 0 else 0 for _2 in range(s + 1)] for _1 in range(n+1)]

MOD = 998244353

for i, ai in enumerate(a):
  for j, v in enumerate(dp[i]):
    dp[i + 1][j] += v
    dp[i + 1][j] %= MOD 
    if j + ai <= s:
      dp[i + 1][j + ai] += v
      dp[i + 1][j + ai] %= MOD


print(sum(dp_i[s] for dp_i in dp) % MOD)
### BUGGY CODE ###

import collections
s = list(input())
n = len(s)
check = True
counter = 0
while check:
    temp = False
    for i in range(n-1):
        if s[i] == "B" and s[i+1] == "W":
            s[i] = "W"
            s[i+1] = "B"
            counter += 1
            temp = True
    if temp == False:
        check = False
print(counter)

### FIXED CODE ###

s = list(input())
b = 0
ans = 0
for i in range(len(s)):
    if s[i] == "B":
        b += 1
    else:
        ans += b
print(ans)
### BUGGY CODE ###

def solve():
  while True:
    n,m = map(int,input().split())
    if not n and not m: break
    lst = []
    lst2 = []
    for i in range(n):
      x = int(input())
      if x <= m:
        lst.append(x)
    lst2 = [i + j for i in lst for j in lst if i <= j]
    #for i in lst:
    #  for j in lst:
    #    if i + j <= m:
    #      lst2.append(i + j)
    #lst2 = list(set(lst2 + lst))
    lst2.sort()
    def binary(x, left, right):
      center = (left + right) // 2
      length = right - left + 1
      v = lst2[center]
      if length == 1 or length == 2:
        if v > x:
          return center - 1
        else:
          return center
      elif v == x: return x
      elif v < x: return binary(x, center + 1, right)
      elif v > x: return binary(x, left, center - 1)
    A = []
    #ans = 0
    for i in lst2:
      if i + lst2[-1] <= m:
        A.append(i + lst2[-1])
        #ans = max(ans, i + lst2[-1])
      elif i <= m:
        A.append(i + lst2[binary(m - i, 0 , len(lst2) - 1)])
        #ans = max(ans, i + lst2[binary(m - i, 0, len(lst2) - 1)])
      else:
        break
    print(max(A))
    #print(ans)
solve()




### FIXED CODE ###

def solve():
  while True:
    n,m = map(int,input().split())
    if not n and not m: break
    
    lst = [int(input()) for _ in range(n)]
    lst.append(0)
    lst = sorted(lst)
    lst2 = [i + j for i in lst for j in lst if i <= j]
    lst2 = sorted(lst2)
    A = []
    index = len(lst2) - 1
    for i in lst2:
      if i + lst2[-1] <= m:
        A.append(i + lst2[-1])
      elif i <= m:
        while True:
          if i + lst2[index] <= m:
            break
          index -= 1
        A.append(i + lst2[index])
      else:
        break
    print(max(A))
solve()
### BUGGY CODE ###

from math import gcd

n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6


def sieve(x):
    """
    Sieve of Eratosthenes
    :param x: max value
    :return: list of bool
    """

    is_prime = [True] * (x + 1)
    is_prime[0] = is_prime[1] = False

    for i in range(2, x + 1):
        if is_prime[i]:
            for j in range(i * 2, x + 1, i):
                is_prime[j] = False

    return is_prime


is_prime = sieve(MAX)
primes = [i for i, e in enumerate(is_prime) if e]

bl = True
for e in a:
    nxt = []
    for e2 in primes:
        if e % e2 != 0:
            nxt.append(e2)
        else:
            while e % e2 == 0:
                e //= e2

    if e != 1:
        bl = False

    primes = nxt

g = a[0]
for e in a:
    g = gcd(g, e)

if g == 1 and bl:
    ans = "pairwise coprime"
elif g == 1:
    ans = "setwise coprime"
else:
    ans = "not coprime"

print(ans)


### FIXED CODE ###

from math import gcd
import numpy as np
from numba import njit

n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6

g = a[0]
for e in a:
    g = gcd(g, e)

if g != 1:
    print("not coprime")
    exit()

nums = np.zeros(MAX + 1, np.int64)
for e in a:
    nums[e] += 1


@njit
def f(nums):
    for i in range(2, MAX + 1):
        if nums[i::i].sum() > 1:
            return False

    return True


bl = f(nums)

if bl:
    print("pairwise coprime")
else:
    print("setwise coprime")
### BUGGY CODE ###

from math import gcd
K = int(input())
sum = 0
for a in range(K):
    for b in range(K):
        for c in range(K):
            sum += gcd(gcd(a + 1, b + 1), c + 1)
print(sum)


### FIXED CODE ###

from math import gcd
K = int(input())
sum = 0
for a in range(K):
    for b in range(K):
        g = gcd(a + 1, b + 1)
        for c in range(K):
            sum += gcd(g, c + 1)
print(sum)
### BUGGY CODE ###

import math
k=int(input())
ans=0
for x in range(1,k+1):
    for y in range(1,k+1):
        for z in range(1,k+1):
           if math.gcd(x,y)==1:
               ans+=1
           elif math.gcd(math.gcd(x,y),z)==1:
               ans+=1
           else:
              ans+=math.gcd(math.gcd(x,y),z)
print(ans)

### FIXED CODE ###

import numpy as np
K=int(input())
x = np.arange(1, K + 1)
nums = np.gcd.outer(np.gcd.outer(x, x), x)
print(nums.sum())
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
l = [0] * q
r = [0] * q
for i in range(0, q):
    l[i], r[i] = map(int, input().split())
ac_index = []
for i in range(n - 1):
    if s[i] + s[i + 1] == 'AC':
        ac_index.append(i)
for i in range(0, q):
    count = 0;
    for j in ac_index:
        if l[i] - 1 <= j <  r[i] - 1:
            count += 1
    print(count)

### FIXED CODE ###

n, q = map(int, input().split())
s = ' ' + input()
heap = [0] * (n + 1)
cnt = 0
for i in range(2, n + 1):
    if s[i - 1] == 'A' and s[i] == 'C':
        cnt += 1;
    heap[i] = cnt
ans = []
for i in range(q):
    l, r = map(int, input().split())
    ans.append(heap[r] - heap[l])
for i in ans:
    print(i)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for i in range(N//R + 1):
    for j in range(N//G + 1):
        if i*R + j*G <= N and (N - (i*R + j*G)) % B == 0:
            ans += 1
print(ans)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
 
ans = 0
for i in range(N//R + 1):
    for j in range(N//G + 1):
        if i*R + j*G > N:
            break
        if i*R + j*G <= N and (N - (i*R + j*G)) % B == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

from collections import deque
N, X, Y=map(int, input().split())
ans=[0 for _ in range(N)]
link=[[]]+[[2]]+[[i-1, i+1] for i in range(2, N)]+[[N-1]]
link[X].append(Y)
link[Y].append(X)

def f(p, length, moto):
  ans[length]+=1
  for data in link[p]:
    if kisyutu[data]==0:
      kisyutu[data]=1
      q.append([data, length+1, p])

for i in range(1, N+1):
  kisyutu=[1]+[0 for i in range(N)]
  kisyutu[i]=1
  q=deque()
  for data in link[i]:
    q.append([data, 1, i])
    kisyutu[data]=1
  while len(q)>0:
    data=q.popleft()
    f(data[0], data[1], data[2])
    
ans=[ans[i]//2 for i in range(N)]
print(*ans[1:], sep='\n')

### FIXED CODE ###

from collections import deque
N, X, Y=map(int, input().split())
ans=[0 for _ in range(N)]
link=[[]]+[[2]]+[[i-1, i+1] for i in range(2, N)]+[[N-1]]
link[X].append(Y)
link[Y].append(X)

def f(p, length, moto):
  ans[length]+=1
  for data in link[p]:
    if kisyutu[data]==0:
      kisyutu[data]=1
      q.append([data, length+1, p])

for i in range(1, N+1):
  kisyutu=[1]+[0 for i in range(N)]
  kisyutu[i]=1
  q=deque()
  for data in link[i]:
    q.append([data, 1, i])
    kisyutu[data]=1
  while len(q)>0:
    data=q.popleft()
    f(data[0], data[1], data[2])
    
ans=[ans[i]//2 for i in range(N)]
print(*ans[1:], sep='\n')
### BUGGY CODE ###

#!/usr/bin/env python3
# coding=utf-8

import sys
import random

import functools


@functools.lru_cache(100000)
def is_prime3(q, k=10):
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False

    d = (q - 1) >> 1
    while d & 1 == 0:
        d >>= 1

    for i in range(k):
        a = random.randint(1, q - 1)
        t = d
        y = pow(a, t, q)
        while t != q - 1 and y != 1 and y != q - 1:
            y = pow(y, 2, q)
            t <<= 1
        if y != q - 1 and t & 1 == 0:
            return False
    return True


q = int(sys.stdin.readline().strip())
for _ in range(q):
    l, r = sys.stdin.readline().strip().split(" ")
    l = int(l)
    r = int(r)
    ans = 0
    for i in range(l, r + 1, 2):
        if is_prime3((i + 1) // 2) and is_prime3(i):
            ans += 1
    print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
# coding=utf-8

import sys

import numpy as np

num_max = 100000
primes = np.asarray([True for _ in range(num_max + 1)])
for i in range(num_max + 1):
    if i == 0 or i == 1:
        primes[i] = False
    else:
        primes[i * 2::i] = False
primes = set(np.arange(num_max + 1)[primes])
like2017 = [1 if i in primes and (i + 1) // 2 in primes else 0 for i in range(num_max + 1)]
cumsum = np.cumsum(like2017)

q = int(sys.stdin.readline().strip())
for _ in range(q):
    l, r = sys.stdin.readline().strip().split(" ")
    l = int(l)
    r = int(r)
    print(cumsum[r] - cumsum[l - 1])
### BUGGY CODE ###

import math
N=int(input())
total=[]
candi=[]

for i in range(1,N+1):
  for j in range(1,N+1):
    for k in range(1,N+1):
      ans=math.gcd(math.gcd(i,j),k)
      total.append(ans)
      
print(sum(total))

### FIXED CODE ###

from math import gcd
N=int(input())
total=0

for i in range(1,N+1):
  for j in range(1,N+1):
    for k in range(1,N+1):
      total+=gcd(gcd(i,j),k)
      
print(total)
### BUGGY CODE ###

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

K = min(K,50)
for k in range(K):
  light = [0] * N
  for i in range(N):
    start = max(0,i-A[i])
    end = min(N-1, i+A[i])
    for j in range(start, end+1):
      light[j] += 1
    
  A = light

print(" ".join(map(str,light)))


### FIXED CODE ###

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

import math
K = min(K, 43)
for k in range(K):
  light = [0] * (N+1)
  for i in range(N):
    start = max(0,i-A[i])
    end = min(N-1, i+A[i])
    light[start] += 1
    light[end+1] -= 1
  for i in range(1,N):
    light[i] += light[i-1]
    
  A = light

light.pop()
print(" ".join(map(str,light)))