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

import itertools
n,m,q = map(int,input().split())
ch = list(itertools.combinations_with_replacement(range(1,m+1),n))
lch = len(ch)
rel = [0]*lch
l = [list(map(int,input().split())) for _ in range(q)]
for k in range(lch):
    for i in range(q):
        a = l[i][0]
        b = l[i][1]
        c = l[i][2]
        d = l[i][3]
        if ch[k][b-1]-ch[k][a-1]==c:
            rel[k]+=d
print(max(rel))

### FIXED CODE ###

import itertools
n,m,q = map(int,input().split())
ch = list(itertools.combinations_with_replacement(range(1,m+1),n))
lch = len(ch)
rel = [0]*lch
l = [list(map(int,input().split())) for _ in range(q)]
for k in range(lch):
    for i in range(q):
        if ch[k][l[i][1]-1]-ch[k][l[i][0]-1]==l[i][2]:
            rel[k]+=l[i][3]
print(max(rel))
### BUGGY CODE ###

import numpy as np
H, N = map(int, input().split())

dp = [float('inf')]*(H+1)
dp[0] = 0
for i in range(N):
    a, b = map(int, input().split())
    dp[1:a+1] = np.minimum(dp[1:a+1], b)
    for j in range(a+1, H+1):
        dp[j] = min(dp[j], dp[j-a]+b)
print(int(dp[-1]))


### FIXED CODE ###

H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
max_a = max(a for a, b in ab)
dp = [0]*(H+max_a)
for i in range(1, H+max_a):
    dp[i] = min(dp[i-a]+b for a, b in ab)
print(dp[H])
### BUGGY CODE ###

class Range_BIT:
    def __init__(self, n):
        self.n = n
        self.bit0 = [0]*(n+1)
        self.bit1 = [0]*(n+1)
    
    def _Add(self, k, x, is_bit0=True):
        if is_bit0 == True:
            data = self.bit0
        else:
            data = self.bit1
        while k <= self.n:
            data[k] += x
            k += k & -k
    
    def _Get(self, data, k):
        s = 0
        while k:
            s += data[k]
            k -= k&-k
        return s
    
    """ 配列の獲得 """
    def Array(self):
        array = [0]*(n+1)
        for i in range(self.n):
            array[i] = self.Get(i+1,i+2)
        return array[:-1]
    
    """ 区間[l:r)に対してxを加算 """
    def Add(self, l, r, x):
        self._Add(l, -x*(l-1), is_bit0=True)
        self._Add(r, x*(r-1), is_bit0=True)
        self._Add(l, x, is_bit0=False)
        self._Add(r, -x, is_bit0=False)
    
    """ 区間[l:r)の総和 """
    def Get(self, l, r):
        Pi = self._Get(self.bit1, r-1)*(r-1) - self._Get(self.bit1, l-1)*(l-1)
        Qi = self._Get(self.bit0, r-1) - self._Get(self.bit0, l-1)
        return Pi+Qi


n,k = map(int,input().split())
A = list(map(int,input().split()))
for j in range(k):
    if j==0:
        rbit = Range_BIT(n)
        for i,a in enumerate(A):
            rbit.Add(max(1,i+1-a), min(i+2+a, n+1), 1)
    else:
        A_ = rbit.Array()
        rbit = Range_BIT(n)
        for i,a in enumerate(A_):
            rbit.Add(max(1,i+1-a), min(i+2+a, n+1), 1)
print(*rbit.Array())

### FIXED CODE ###

n,k = map(int,input().split())
A = list(map(int,input().split()))
imos = [0]*(n+1)
for j in range(k):
    if j==0:
        arr = A
    else:
        arr = imos
    imos = [0]*(n+1)
    for i,a in enumerate(arr):
        imos[max(i-a, 0)] += 1
        imos[min(i+a+1, n)] -= 1
    for k in range(1, len(imos)):
        imos[k] = imos[k]+imos[k-1]
    imos = imos[:-1]
    if set(imos)=={n}:
        break
print(*imos)
### BUGGY CODE ###

#template
def inputlist(): return [int(k) for k in input().split()]
#template
N,X,Y = inputlist()
cost = [[10**5]*(N) for _ in range(N)]
for i in range(N-1):
    cost[i][i+1] = 1
    cost[i+1][i] = 1
cost[X-1][Y-1] = 1
cost[Y-1][X-1] = 1
def dijkstra(s,n,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0

    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True

        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d
li = [0]*N
for i in range(N):
    d = dijkstra(i,N,cost)
    li[i] = d
dic = {n:0 for n in range(1,N)}
for i in range(N):
    for j in range(N):
        if li[i][j] == 0:
            continue
        dic[li[i][j]] +=1
for i in range(1,N):
    print(dic[i]//2)

### FIXED CODE ###

#template
def inputlist(): return [int(j) for j in input().split()]
#template
#issueから始める
N,X,Y = inputlist()
graph = [[] for _ in range(N+1)]
for i in range(1,N):
    graph[i].append(i+1)
    graph[i+1].append(i)
graph[X].append(Y)
graph[Y].append(X)
seen = [False]*(N+1)
ans = [0]*(N+1)
def bfs(i):
    from collections import deque
    que = deque()
    que.append([i,0])
    seen[i] = True
    while len(que)!=0:
        li = que.popleft()
        x = li[0]
        count = li[1]
        for j in graph[x]:
            if seen[j]:
                continue
            seen[j] = True
            counta= count + 1
            que.append([j,counta])
            ans[counta]+=1
for i in range(1,N+1):
    seen = [False]*(N+1)
    bfs(i)
for i in range(1,N):
    print(ans[i]//2)
### BUGGY CODE ###

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

dp = [0 for _ in range(N)]
for i in range(1, N):
    r = max(0, i - K)
    dp[i] = min(d + abs(H[i] - h) for h, d in zip(H[r:i], dp[r:i]))
print(dp[N-1])

### FIXED CODE ###

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

dp = [0 for _ in range(N)]
for i, hi in enumerate(H):
    if i == 0:
        continue
    r = max(0, i - K)
    dp[i] = min(d + abs(hi - h) for d, h in zip(dp[r:i], H[r:i]))
print(dp[N-1])
### BUGGY CODE ###

from collections import defaultdict, deque, Counter

N = int(input())

edges = {}
counter = Counter()
nodes = defaultdict(set)

K = 0
for i in range(N - 1):
    u, v = map(int, input().split(' '))
    counter[u] += 1
    counter[v] += 1
    K = max(K, counter[u], counter[v])
    nodes[u].add(v)
    nodes[v].add(u)
    edges[(u, v)] = i

colors = set([1 + k for k in range(K)])
checked = set()
queue = deque([(1, 0)])
edge_colors = [0] * N

while queue:
    u, uc = queue.popleft()
    checked.add(u)
    if len(checked) == N:
        break
    for v, vc in zip(nodes[u] - checked, colors - {uc}):
        edge_colors[edges[(min(u, v), max(u, v))]] = vc
        queue.append((v, vc))

print(K)
for i in range(N - 1):
    print(edge_colors[i])


### FIXED CODE ###

from collections import defaultdict, deque, Counter

N = int(input())

counter = Counter()
nodes = defaultdict(list)
edges = []

for i in range(N - 1):
    u, v = map(int, input().split(' '))
    nodes[u].append((v, i))
    nodes[v].append((u, i))
    edges.append((u, v))

K = 0
for node in nodes.values():
    K = max(K, len(node))

checked = set()
queue = deque([(1, 0)])
edge_colors = [0] * N

while queue:
    u, uc = queue.popleft()
    checked.add(u)
    color = 1
    for v, e in nodes[u]:
        if v in checked:
            continue
        if color == uc:
            color += 1
        edge_colors[e] = color
        queue.append((v, color))
        color += 1

print(K)
for i in range(N - 1):
    print(edge_colors[i])
### BUGGY CODE ###

n, m = (int(_) for _ in input().split())
ab_list = [[int(i) for i in input().split()] for i in range(n)]

ab_list = sorted(ab_list)

buy = 0
money = 0
j = 0
lst = []

for i in range(n):
    lst.append(ab_list[n - i - 1][1])
    b_sum = sum(lst)

while (buy < m):
    buy += ab_list[j][1]
    money += ab_list[j][0] * ab_list[j][1]
    j += 1

print(money-(ab_list[j-1][0]*(buy-m)))


### FIXED CODE ###

n, m = (int(_) for _ in input().split())
ab_list = [[int(i) for i in input().split()] for i in range(n)]

ab_list = sorted(ab_list)

buy = 0
money = 0
j = 0


while (buy < m):
    buy += ab_list[j][1]
    money += ab_list[j][0] * ab_list[j][1]
    j += 1

print(money-(ab_list[j-1][0]*(buy-m)))
### BUGGY CODE ###

from itertools import product

X, Y, Z, K = map(int, input().split())
lst_A = list(map(int, input().split()))
lst_B = list(map(int, input().split()))
lst_C = list(map(int, input().split()))


lst_AB = [a+b for a, b in product(lst_A, lst_B)]
lst_AB.sort(reverse=True)
lst_AB_K = lst_AB[:min(3000, X*Y*Z)]


lst_ABC = [ab+c for ab, c in product(lst_AB_K, lst_C)]
lst_ABC.sort(reverse=True)


print(*lst_ABC[:K], sep="\n")


### FIXED CODE ###

import sys
from itertools import product


X, Y, Z, K = map(int, input().split())
lst_A = list(map(int, input().split()))
lst_B = list(map(int, input().split()))
lst_C = list(map(int, input().split()))
lst_A.sort(reverse=True)
lst_B.sort(reverse=True)
lst_C.sort(reverse=True)

# lst_A_K = lst_A[:K]
# lst_B_K = lst_B[:K]
lst_C_K = lst_C[:K]


lst_AB = sorted([a+b for a, b in product(lst_A, lst_B)], reverse=True)
lst_AB_K = lst_AB[:K]

lst_ABC = sorted([ab+c for ab, c in product(lst_AB_K, lst_C_K)], reverse=True)
lst_ABC_K = lst_ABC[:K]

print(*lst_ABC_K, sep="\n")
### BUGGY CODE ###

N=int(input())
y=list(map(int, input().split()))
y.sort()
ans=0
for i in range(N-2):
  for j in range(i+1, N-1):
    tmp=y[i]+y[j]
    for k in range(j+1, N):
      if y[k]<tmp:
        ans+=1
      else:
        break
print(ans)

### FIXED CODE ###

import bisect as bs
N=int(input())
y=list(map(int, input().split()))
y.sort()
ans=0
for i in range(N-2):
  for j in range(i+1, N-1):
    tmp=y[i]+y[j]
    ans+=bs.bisect_left(y[(j+1):],tmp)
    
print(ans)
### BUGGY CODE ###

from copy import deepcopy

n, m = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
x = [[int(i) for i in input().split()] for j in range(m)]

x_ = deepcopy(x)
tree = []
memo = []

try:
    for i, y in enumerate(x_):
        if y in memo:
            continue
        tree.append(set(y))
        while True:
            prev = tree[i]
            for j in x_[i+1:]:
                if tree[i] & set(j):
                    tree[i] = tree[i] | set(j)
                    memo.append(j)

            if not tree[i] - prev:
                break
except:
    pass

for i in tree:
    i = list(i)
    temp = [p[j-1] for j in i]
    for j in i:
        if j in temp:
            p[j-1] = j

ans = 0

for i, p_ in enumerate(p):
    if i+1 == p_:
        ans += 1

print(ans)

### FIXED CODE ###

n, m = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
x = [[int(i) for i in input().split()] for j in range(m)]

par = [i for i in range(0, n+1)]

def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x]

def unite(x, y):
    x = root(x)
    y = root(y)
    if x != y:
        par[x] = y

for i in x:
    a, b = i
    unite(a, b)

ans = 0
for i, p_ in enumerate(p):
    if root(i+1) == root(p_):
        ans += 1

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

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

loop_counter = 0 # 何回目でループに達するか

start = 1
end = a[start-1]
road = [1]
while True:
    if end in road:
        # ループしている
        roop_start = end
        break
    else:
        road.append(end)
        start = end
        end = a[start-1]
roop_start_index = road.index(roop_start)
roop_length = len(road)-road.index(roop_start)
if k <= roop_start_index+1:
    print(road[k])
else:
    k -= roop_start_index
    k %= roop_length
    print(road[roop_start_index+k])


### FIXED CODE ###

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

loop_counter = 0 # 何回目でループに達するか

start = 1
end = a[start-1]
is_checked = [0 for _ in range(n)]
is_checked[0] = 1
road = [1]
while True:
    if is_checked[end-1] == 1:
        # ループしている
        roop_start = end
        break
    else:
        road.append(end)
        is_checked[end-1] = 1
        start = end
        end = a[start-1]
roop_start_index = road.index(roop_start)
roop_length = len(road)-roop_start_index
if k <= roop_start_index+1:
    print(road[k])
else:
    k -= roop_start_index
    k %= roop_length
    print(road[roop_start_index+k])
### BUGGY CODE ###

n=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s

def bitadd(BIT,i,x):
  while i<=2**n:
    BIT[i]+=x
    i+=i&(-i)
  return BIT
nn=2**n
ans=float("inf")
for i in range(nn):
  E,O=[],[]
  for j in range(n):
    if i&(1<<j)==0:
      if j%2==0:
        E.append(A[j]*10000+j*100+0)
      else:
        O.append(A[j]*10000+j*100+0)
    else:
      if j%2==0:
        O.append(B[j]*10000+j*100+1)
      else:
        E.append(B[j]*10000+j*100+1)

  E.sort()
  O.sort()
  C=[]

  chk=True
  if len(E)!=(n+1)//2:
    chk=False
  else:
    for i in range(n):
      if i%2==0:
        C.append(E[i//2])
      else:
        C.append(O[i//2])
    for ii in range(n-1):
      if C[ii]//10000>C[ii+1]//10000:
        chk=False
        break
    
  if chk:
    ct=0
    BIT=[0]*nn
    BIT.insert(0,0)
    for i1 in range(n):
      c=(C[i1]%10000)//100+1
      ct+=i1-bitsum(BIT,c)
      bitadd(BIT,c,1)


    
    ans=min(ans,ct)
print(-1 if ans==float("inf") else ans)



### FIXED CODE ###

import itertools
n=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s

def bitadd(BIT,i,x):
  while i<=64:
    BIT[i]+=x
    i+=i&(-i)
  return BIT

def tentou(X):
  ret=0
  BIT=[0]*64
  BIT.insert(0,0)
  for i1 in range(n):
    x=X[i1]+1
    ret+=i1-bitsum(BIT,x)
    bitadd(BIT,x,1)
  return ret
N=[int(i) for i in range(n)]
nn=2**n
ans=float("inf")
for _ in range(n//2+1):
  for com in itertools.combinations(N,2*_):
    i=0
    for ura in com:
      i+=2**ura
    E,O=[],[]
    for j in range(n):
      if i&(1<<j)==0:
        if j%2==0:
          E.append(A[j]*100+j)
        else:
          O.append(A[j]*100+j)
      else:
        if j%2==0:
          O.append(B[j]*100+j)
        else:
          E.append(B[j]*100+j)
    if len(E)!=(n+1)//2:
      continue
    else:
      E.sort()
      O.sort()

      chk=True
      C=[E[0]%100]
      prev=E[0]//100
      for i in range(1,n):
        ii=i//2
        if i%2==0:
          C.append(E[ii]%100)
          if E[ii]//100<prev:
            chk=False
            break
          else:
            prev=E[ii]//100
        else:
          C.append(O[ii]%100)
          if O[ii]//100<prev:
            chk=False
            break
          else:
            prev=O[ii]//100
    
    if chk:
      ans=min(ans,tentou(C))
print(-1 if ans==float("inf") else ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)


def i1str():
    return input()


def istrs(n=None):
    if n is None:
        return input().split()
    a = []
    for _ in range(n):
        a.append(istrs())
    return a


def i1num():
    return int(input())


def inums(n=None):
    if n is None:
        return list(map(int, input().split()))
    a = []
    for _ in range(n):
        a.append(inums())
    return a


def ostrs(l, sp=" "):
    print(sp.join(l))


def onums(l, sp=" "):
    print(sp.join(map(str, l)))


def solve(aii, index, left, right):
    res = 0
    ai, i = aii[index]
    if index == 0:
        return ai * abs(i-left)

    index -= 1
    # to leftmost
    res1 = ai * abs(i-left) + solve(aii, index, left+1, right)
    # to rightmost
    res2 = ai * abs(right-i) + solve(aii, index, left, right-1)
    return max(res1, res2)


if __name__ == "__main__":
    n = i1num()
    a = inums()
    aii = sorted((a[i], i)for i in range(n))
    print(solve(aii, n-1, 0, n-1))


### FIXED CODE ###

def i1str():
    return input()


def istrs(n=None):
    if n is None:
        return input().split()
    a = []
    for _ in range(n):
        a.append(istrs())
    return a


def i1num():
    return int(input())


def inums(n=None):
    if n is None:
        return list(map(int, input().split()))
    a = []
    for _ in range(n):
        a.append(inums())
    return a


def ostrs(l, sp=" "):
    print(sp.join(l))


def onums(l, sp=" "):
    print(sp.join(map(str, l)))


def solve(n, aii):
    dp = [[0 for _ in range(n+1)] for _ in range(n+1)]

    for x in range(1, n+1):
        ai, i = aii[x-1]
        dp[x][0] = dp[x-1][0] + ai * (i-x+1)
        dp[0][x] = dp[0][x-1] + ai * (n-x-i)

    for s in range(1, n+1):
        for x in range(1, s):
            y = s - x
            ai, i = aii[s-1]
            dp[x][y] = max(dp[x-1][y] + ai * (i-x+1),
                           dp[x][y-1] + ai * (n-y-i))

    res = 0
    for x in range(n+1):
        if dp[x][n-x] > res:
            res = dp[x][n-x]
    return res


if __name__ == "__main__":
    n = i1num()
    a = inums()
    aii = sorted([(a[i], i)for i in range(n)], reverse=True)
    print(solve(n, aii))
### BUGGY CODE ###

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

l.sort()
cnt = 0
import itertools
import bisect
for a, b in itertools.combinations(l, r=2):
  l_woab = l[:]
  l_woab.remove(a)
  l_woab.remove(b)
  if False:
    print(a, b, end=' : ')
    print(l_woab)
    print(bisect.bisect_left(l_woab, a + b ), bisect.bisect_left(l_woab, b))
  
  cnt += max(bisect.bisect_left(l_woab, a + b ) -
             bisect.bisect_left(l_woab, b), 0)

print(cnt)


### 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):
    a=l[i]
    b=l[j]
    le=bisect.bisect_left(l,max(a-b,b-a)+1)
    ri=bisect.bisect_right(l,a+b-1)
    #print(le,ri)
    f=0
    if le<=i<=ri:
      f-=1
    if le<=j<=ri:
      f-=1
    if ri-le+f>0:
      ans+=ri-le+f
    #print(a,b,ans)

print(ans//3)
### BUGGY CODE ###

from math import factorial
X, Y = map(int,input().split())
if (X+Y)%3!=0:
    print(0)
else:
    itr=(X+Y)//3
    x_mx=itr*2
    if itr<=X and X<=x_mx and itr<=Y and Y<=x_mx and X+Y==itr+x_mx:
        c=X-itr
        n=factorial(itr)
        r=factorial(c)
        n_r=factorial(itr-c)
        f=(n//(r*n_r))%(10**9+7)
        print(f)
    else:
        print(0)

### FIXED CODE ###

X, Y = map(int,input().split())
# https://qiita.com/derodero24/items/
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

if (X+Y)%3!=0:
    print(0)
else:
    itr=(X+Y)//3
    x_mx=itr*2
    if itr<=X and X<=x_mx and itr<=Y and Y<=x_mx and X+Y==itr+x_mx:
        c=X-itr
        f=cmb(itr, c)
        f=f%(10**9+7)
        print(f)
    else:
        print(0)
### BUGGY CODE ###

#
import random


def main():
    n = int(input())
    agrid = []
    agrid_pointer = [0] * n

    for i in range(n):
        al = list(map(int, input().split()))
        for j in range(len(al)):
            al[j] -= 1
        agrid.append(al)

    ans = 0
    targets = list(range(n))
    random.shuffle(targets)

    while True:
        match = set()
        for i in range(n):
            if agrid_pointer[i] == n - 1 or i in match:  # もう全部対戦済み or この日対戦済み
                continue

            target = agrid[i][agrid_pointer[i]]
            if agrid_pointer[target] == n - 1 or target in match:  # もう全部対戦済み or この日対戦済み
                continue
            # i, target は対戦可能

            if agrid[target][agrid_pointer[target]] != i:
                continue

            # can match
            agrid_pointer[i] += 1
            agrid_pointer[target] += 1

            match.add(i)
            match.add(target)

            if len(match) == n or len(match) == n - 1:  # 全員試合することが決まったら
                break

        # print(match)
        if len(match) == 0:  # 対戦がなくなったら
            break
        ans += 1

    # print(aconditions)
    # 対戦が残ってたら
    for p in agrid_pointer:
        if p != n - 1:
            print(-1)
            return
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#
import sys
import time

def input(): return sys.stdin.readline().strip()

def main():
    n = int(input())
    agrid = []
    agrid_pointer = [0] * n

    start = time.time()

    for i in range(n):
        al = list(map(int, input().split()))
        agrid.append(al)

    ans = 0

    while True:
        match = set()
        for i in range(n):
            if agrid_pointer[i] == n - 1 or i in match:  # もう全部対戦済み or この日対戦済み
                continue

            target = agrid[i][agrid_pointer[i]] - 1
            if agrid_pointer[target] == n - 1 or target in match:  # もう全部対戦済み or この日対戦済み
                continue
            # i, target は対戦可能

            if agrid[target][agrid_pointer[target]] - 1 != i:
                continue

            # can match
            agrid_pointer[i] += 1
            agrid_pointer[target] += 1

            match.add(i)
            match.add(target)

            if len(match) == n or len(match) == n - 1:  # 全員試合することが決まったら
                break

        # print(match)
        if len(match) == 0:  # 対戦がなくなったら
            break
        elapsed_time = time.time() - start
        if elapsed_time > 1.5:
            print(n * (n-1)//2)
            return

        ans += 1

    # print(aconditions)
    # 対戦が残ってたら
    for p in agrid_pointer:
        if p != n - 1:
            print(-1)
            return
    print(ans)


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

s = input()
l = len(s)
key = [0]*2019
for i in range(l):
  n = int(s[l-i-1:])
  k = n%2019
  key[k] += 1

ans = key[0]
for i in range(2019):
  if key[i] >= 2:
    ans += key[i]*(key[i]-1)//2
print(ans)

### FIXED CODE ###

n = input()
l = len(n)
key = [0]*2019
mod = 1
judge = 0
for i in range(l):
  judge += ((mod%2019)*int(n[l-i-1]))%2019
  judge %= 2019
  k = judge%2019
  key[k] += 1
  mod *= 10
  mod %= 2019

ans = key[0]
for i in range(2019):
  if key[i] >= 2:
    ans += key[i]*(key[i]-1)//2
print(ans)
### BUGGY CODE ###

from math import factorial as f
from sys import exit


bign = 10**9+7
n,k = map(int,input().split())

edge = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)

if len(edge[1]) > k-1:
    print(0)
    exit()
ans = (f(k)//f(k-1-len(edge[1])))%bign

for i in range(2,n+1):
    if len(edge[i]) > k-1:
        print(0)
        exit()
    if len(edge[i])==1:
        continue

    ans = (ans*f(k-2)//f(k-2-len(edge[i])+1))%bign
print(ans)





### FIXED CODE ###

from math import factorial as f
from sys import exit

def main():
    bign = 10**9+7
    n,k = map(int,input().split())

    edge = [[] for i in range(n+1)]
    for i in range(n-1):
        a,b = map(int,input().split())
        edge[a].append(b)
        edge[b].append(a)

    if len(edge[1]) > k-1:
        print(0)
        exit()
    ans = (f(k)//f(k-1-len(edge[1])))%bign

    for i in range(2,n+1):
        if len(edge[i]) > k-1:
            print(0)
            exit()
        if len(edge[i])==1:
            continue
        t = k-2
        for j in range(len(edge[i])-1):
            ans = ans * t % bign
            t-=1
        
    print(ans)


main()
### BUGGY CODE ###

Q=int(input())
queries=[tuple(map(int,input().split())) for _ in range(Q)]

memo=[-1]*(10**5+1)
memo[1]=0
def is_prime(n):
    if memo[n]!=-1:
        return(memo[n]==1)
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            memo[n]=0
            return False
    memo[n]=1
    return True

for l,r in queries:
    ans=0
    for n in range(l,r+1):
        if n&1:
            if is_prime(n) and is_prime((n+1)//2):
                ans+=1
    print(ans)


### FIXED CODE ###

Q=int(input())
queries=[tuple(map(int,input().split())) for _ in range(Q)]

#エラトステネスの篩
p=[True]*(10**5+1)
p[0]=False
p[1]=False
for i in range(2,10**5+1):
    if p[i]:
        for j in range(2*i, 10**5+1, i):
            p[j]=False

#like2017[n]=n以下の「2017に似た数」の数
like2017=[0]*(10**5+1)
for i in range(1,10**5+1):
    like2017[i]=like2017[i-1]+(1 if i&1 and p[i] and p[(i+1)//2] else 0)

for l,r in queries:
    print(like2017[r]-like2017[l-1])