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

import sys
def main():
  input = sys.stdin.readline
  sys.setrecursionlimit(10**7)
  n,k = map(int,input().split())
  sl = [0]*n
  dl = [0]*n
  tree = [[] for i in range(n)]
  mod = 10**9+7

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

  def perm(n, k = 1):
    pdt = 1
    if n != int(n) or k != int(k):
      raise ValueError("perm() not defined for float object")
    elif k < 0:
      pdt = 0
    elif n < 0:
      pdt = 0
    else:
      for x in range(n, n-k, -1):
        pdt *= x
    return pdt

  def dfs(x,depth,k):
    sl[x] = 1
    dl[depth] += 1
    child = 0
    ans = 1
    for i in tree[x]:
      if sl[i] == 0:
        ans *= dfs(i,depth+1,k)
        ans %= mod
        child += 1
    if depth == 0:
      ans *= perm(k-1,child)
      ans %= mod
    else:    
      ans *= perm(k-2,child)
      ans %= mod
    return ans

  print(dfs(0,0,k)*k%mod)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
mod = 10**9+7

def main():
  
  n,k = map(int,input().split())
  sl = [0]*(n+1)
  tree = [[] for i in range(n+1)]
  
  for i in range(n-1):
    a,b = map(int,input().split())
    tree[a] += (b,)
    tree[b] += (a,)

  def dfs(x,depth,k):
    sl[x] = 1
    child = 0
    ans = 1
    for i in tree[x]:
      if sl[i] == 0:
        ans *= dfs(i,depth+1,k)
        child += 1
    if depth == 0:
      for x in range(k-1, k-1-child, -1):
        ans = ans * x % mod   
    else:    
      for x in range(k-2, k-2-child, -1):
        ans = ans * x % mod
    ans %= mod
    return ans

  print(dfs(1,0,k)*k%mod)

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

import sys
si = sys.stdin.readline


def main():
    n = int(si())
    l = [int(e) for e in si().split()]
    mod, ans = 10**9+7, 0
    for i in range(n):
        for j in range(i+1, n):
            ans = (ans+(l[i]*l[j]) % mod) % mod
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
si = sys.stdin.readline


def main():
    n = int(si())
    l = [int(e) for e in si().split()]
    tot = sum(l)
    mod, ans = 10**9+7, 0
    for i in range(n-1):
        h = l[i]
        tot -= h
        ans = (ans+(tot*h) % mod) % mod
    print(ans)


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

from collections import defaultdict
from fractions import Fraction
import sys
input = sys.stdin.readline
N=int(input())
mod=10**9+7
dic=defaultdict(lambda: [0,0])
c=0
d=0
e=0
for i in [0]*N:
 A,B = map(int,input().split())
 if A==0 and B==0:
  e+=1
 elif A==0:
  c+=1
 elif B==0:
  d+=1
 else:
  if Fraction(A,B)>0:
   dic[Fraction(A,B)][0]+=1
  else:
   dic[Fraction(-B,A)][1]+=1
ans=1
for k in dic:
 ans*=(pow(2,dic[k][0],mod)+pow(2,dic[k][1],mod) -1)
 ans%=mod
ans*=(pow(2,c,mod)+pow(2,d,mod)-1)
print((ans-1+e)%mod)


### FIXED CODE ###

from collections import defaultdict
from math import gcd
import sys
input = sys.stdin.readline
N=int(input())
mod=10**9+7
dic=defaultdict(lambda: [0,0])
c=0
d=0
e=0
for i in [0]*N:
 A,B = map(int,input().split())
 if A==0 and B==0:
  e+=1
 elif A==0:
  c+=1
 elif B==0:
  d+=1
 else:
  g=gcd(A,B)
  A//=g
  B//=g
  if A*B>0:
   dic[(abs(A),abs(B))][0]+=1
  else:
   dic[(abs(B),abs(A))][1]+=1
ans=1
for k in dic:
 ans=ans*(pow(2,dic[k][0],mod)+pow(2,dic[k][1],mod) -1)
ans=ans*(pow(2,c,mod)+pow(2,d,mod)-1)
print((ans-1+e)%mod)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

n,m,s,t = map(int,input().split())

row = []
col = []
data_e = []
data_s = []
for _ in range(m):
    u,v,a,b = map(int, input().split())
    row.append(u)
    row.append(v)
    col.append(v)
    col.append(u)
    data_e.append(a)
    data_e.append(a)
    data_s.append(b)
    data_s.append(b)

graph_e = csr_matrix((data_e, (row,col)), shape=(n+1, n+1))
graph_s = csr_matrix((data_s, (row,col)), shape=(n+1, n+1))

d_e = dijkstra(csgraph=graph_e, directed=False, indices=s)
d_s = dijkstra(csgraph=graph_s, directed=False, indices=t)

ans = [0] * (n+1)
min_cost = 10**15
for i in range(n,0,-1):
    min_cost = min(min_cost, d_e[i]+d_s[i])
    ans[i] = min_cost

for i in range(1,n+1):
    print(int(10**15 - ans[i]))

### FIXED CODE ###

import sys
input = sys.stdin.readline

n,m,s,t = map(int,input().split())


links_e = [[] for _ in range(n+1)]
links_s = [[] for _ in range(n+1)]
for _ in range(m):
    u,v,a,b = map(int, input().split())
    links_e[u].append((a,v))
    links_e[v].append((a,u))
    links_s[u].append((b,v))
    links_s[v].append((b,u))

# dijkstra
import heapq
def dijkstra(links, start, n):
    inf = 10**10
    d = [inf] * (n+1)
    d[start] = 0
    hq = []
    used = set()
    used.add(start)
    for i in links[start]:
        heapq.heappush(hq, i)
    while(hq):
        cost,i = heapq.heappop(hq)
        if( i in used):
            continue
        d[i] = cost
        used.add(i)
        for tmp in links[i]:
            cost_next, j = tmp
            if(not j in used):
                heapq.heappush(hq, (cost+cost_next, j))
    return d

d_e = dijkstra(links_e, s, n)
d_s = dijkstra(links_s, t, n)

ans = [0] * (n+1)
min_cost = 10**15
for i in range(n,0,-1):
    min_cost = min(min_cost, d_e[i]+d_s[i])
    ans[i] = min_cost

for i in range(1,n+1):
    print(10**15 - ans[i])
### BUGGY CODE ###

h,n = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(n)]
# ありえない値にしたいと仮定すると、最大値が10**7取りうるので10**7+1にする？
dp = [10**8] * (h+1)
dp[0] = 0

for i in range(1,h+1):
    for a,b in ab:
        if i >= a:
            # HPより小さいとき、減らした後のHPに対して消費するMPを足す
            atk = b + dp[i-a]
            if atk < dp[i]:
                dp[i] = atk
        elif b < dp[i]:
            # どの攻撃よりも小さいHPであれば、一番MP消費が少ない攻撃のMPを記録する
            dp[i] = b
# 配列の最後が、求めたいHP
print(dp[-1])

### FIXED CODE ###

h,n = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(n)]
# ありえない値にしたいと仮定すると、最大値が10**7取りうるので10**7+1にする？
dp = [10**8] * (h+1)
dp[0] = 0

for i in range(1,h+1):
    for a,b in ab:
        if i >= a:
            # HPより小さいとき、減らした後のHPに対して消費するMPを足す
            atk = b + dp[i-a]
            if atk < dp[i]:
                dp[i] = atk
        elif b < dp[i]:
            # どの攻撃よりも小さいHPであれば、一番MP消費が少ない攻撃のMPを記録する
            dp[i] = b
# 配列の最後が、求めたいHP
print(dp[-1])
### BUGGY CODE ###

n = int(input())
l = [int(input()) for i in range(n)]
a = [0]
ma = 0
for i in range(len(l)):
    if l[i] > ma:
        ma = l[i]
    a.append(ma)
a.append(0)
b = [0]
ma = 0
for i in range(len(l)):
    if l[-i-1] > ma:
        ma = l[-i-1]
    b.insert(0,ma)
b.insert(0,0)
#print(a,b)
for i in range(n):
    print(max(a[i],b[i+2]))


### FIXED CODE ###

n = int(input())
l = [int(input()) for i in range(n)]
a = [0]
ma = 0
for i,j in enumerate(l):
    if j > ma:
        ma = j
    a.append(ma)
a.append(0)
b = [0]
ma = 0
for i,j in enumerate(reversed(l)):
    if j > ma:
        ma = j
    b.append(ma)
b.append(0)
#print(a,b)
for i in range(n):
    print(max(a[i],b[-i-3]))
### BUGGY CODE ###

import bisect as bs

n = int(input())

a_l = list(map(int, input().split()))
b_l = list(map(int, input().split()))
c_l = list(map(int, input().split()))

a_l.sort()
b_l.sort()
c_l.sort()

ans = 0
for i in range(n):
    index_1 = bs.bisect_right(b_l,a_l[i])
    for j in range(index_1,n):
        index_2 = bs.bisect_right(c_l,b_l[j])
        ans += (n-index_2)
print(ans)


### FIXED CODE ###

import bisect as bs

n = int(input())

a_l = list(map(int, input().split()))
b_l = list(map(int, input().split()))
c_l = list(map(int, input().split()))

a_l.sort()
b_l.sort()
c_l.sort()

ans = 0
for b in b_l:
    ans += bs.bisect_left(a_l,b) * (n-bs.bisect_right(c_l,b))
print(ans)


'''
以下の方法だと、N*logN*logN
for i in range(n):
    index_1 = bs.bisect_right(b_l,a_l[i])
    for j in range(index_1,n):
        index_2 = bs.bisect_right(c_l,b_l[j])
        ans += (n-index_2)
print(ans)
'''
### BUGGY CODE ###

#0<=i<r,0<=j<cで総和求めて引く
#chooseの+2でよい
mod = 10**9+7
def chs(a,b):
    a+=1;b+=1
    a+=b
    res = 1
    for i in range(a,a-b,-1):
        res *= i
        rev = pow(a-i+1,mod-2,mod)
        res *= rev
        res%=mod
    
    return res


r1,c1,r2,c2 = map(int, input().split( ))
r1 -=1;c1-=1
#print(chs(r2,c2),chs(r1,c2),chs(r2,c1),chs(r1,c1))
ans = chs(r2,c2)-chs(r1,c2)-chs(r2,c1)+chs(r1,c1)
ans%=mod

print(ans)

### FIXED CODE ###

#0<=i<r,0<=j<cで総和求めて引く
#chooseの+2でよい
mod = 10**9+7

def chs(a,b):
    a+=1;b+=1
    a+=b
    res = 1
    for i in range(a,a-b,-1):
        res *= i 
        res%=mod
    for i in range(1,b+1):
        res *= rev[i]
        #print(rev[i],pow(i,mod-2,mod))
        res %=mod 
    return res


r1,c1,r2,c2 = map(int, input().split( ))
r1 -=1;c1-=1
if c2>r2:
    r2,c2 = c2,r2
    r1,c1= c1,r1
rev = [pow(i,mod-2,mod) for i in range(c2+5)]###
ans = chs(r2,c2)-chs(r1,c2)-chs(r2,c1)+chs(r1,c1)
ans%=mod
#print(chs(r2,c2),chs(r1,c2),chs(r2,c1),chs(r1,c1))

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

n = int(input())
l = list(map(int,input().split()))
lone = [0]*60
for i in range(n):
  m = l[i]
  for j in range(59,-1,-1):
    if m >= 2**j:
      m = m -2**j
      lone[j] += 1
ans = 0
const = 10**9+7
for i in range(60):
  ans += (2**i*lone[i]*(n-lone[i]))%const
print(ans%const)


### FIXED CODE ###

#O(nm) = O(60n)で解けるはず・・・！
n = int(input())
l = list(map(int,input().split()))
#2進数の桁の出現数をカウントする。
lone = [0]*60
for i in range(n):
  s = bin(l[i])[2:]
  for j in range(len(s)):
    lone[j] += int(s[-j-1])
ans = 0
for i in range(60):
  ans += (2**i*lone[i]*(n-lone[i]))%(10**9+7)
print(ans%(10**9+7))
### BUGGY CODE ###

def score(d,c,s,t):
    ans = 0
    lis = [[0 for j in range(26)] for i in range(d+1)]
    zero = [[] for i in range(26)]
    for i in range(min(d,len(t))):
        ans += s[i][t[i]-1]
        lis[i+1][t[i]-1] = 0
        zero[t[i]-1].append(i+1)
        for j in range(26):
            if t[i]-1 != j:
                lis[i+1][j] = lis[i][j] + 1
                ans -= lis[i+1][j]*c[j] 
    return ans
d = int(input())
c = list(map(int,input().split()))
s = [0]*d
for i in range(d):
    s[i] = list(map(int,input().split()))
t = []
for i in range(d):
    ans = 0
    z = 0
    for j in range(26):
        x = t + [j]
        y = score(d,c,s,x)
        if ans < y:
            ans = y
            z = j
    print(z+1)
    t.append(z)

### FIXED CODE ###

import numpy
d = int(input())
c = list(map(int,input().split()))
s = [0]*d
for i in range(d):
    s[i] = list(map(int,input().split()))
for i in range(d):
    max_index = numpy.argmax(s[i])
    print(max_index+1)
### BUGGY CODE ###

import heapq
def SME(start,end):
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        if None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    i = L
    while i < N :
        if None not in ANS[i:i+L//2+1] :
            i += L//2+1
            continue
        if ANS[i] : continue
        else: ANS[i] = min(Whole[i+1-L:i+1])
        i+=1
    return ANS
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
A = []
parameter = 0.999
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

n = input()
l = list(map(int,input().split()))
ans = 0
for i in range(60):
    c0 = 0
    c1 = 0
    for s in l:
        if bin(s>>i)[-1] == "1":c1 += 1
        else: c0 += 1
    ans += (c1*c0)*(2**i)
print(ans%((10**9)+7))

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
ans = 0
for i in range(60):
    c0 = 0
    c1 = 0
    c1 = sum([1 for a in l if (a>>i) & 1])
    c0 = n - c1
    ans += (c1*c0)*(2**i)
print(ans%((10**9)+7))
### BUGGY CODE ###

#おわり、むり

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

X,Y,Z = [],[],[]
for i in range(N):
    x,y,z = map(int,input().split())
    X.append(x)
    Y.append(y)
    Z.append(z)  
    
    
ans = 0
for fgo in range(0,8):
    FGO = [fgo%2,(fgo//2)%2,(fgo//4)%2]
    dp = [[[0,0,0] for i in range(W+1)] for j in range(N+1)]
    for i in range(W+1):
        dp[0][i][0]= 0 #X
        dp[0][i][1]= 0 #Y
        dp[0][i][2]= 0 #Z
    for i in range(N):
        for w in range(W+1):
            if w>=1:
                x = dp[i][w-1][0]+X[i]
                y = dp[i][w-1][1]+Y[i]
                z = dp[i][w-1][2]+Z[i]
                NOW = (x*pow(-1,FGO[0]))+(y*pow(-1,FGO[1]))+(z*pow(-1,FGO[2]))
                BEFORE = sum([dp[i][w][f]*pow(-1,FGO[f]) for f in range(3)])
                if NOW > BEFORE:
                    dp[i+1][w][0] = x
                    dp[i+1][w][1] = y
                    dp[i+1][w][2] = z
                else:
                    dp[i+1][w][0] = dp[i][w][0]
                    dp[i+1][w][1] = dp[i][w][1]
                    dp[i+1][w][2] = dp[i][w][2]
            else:
                dp[i+1][w][0] = dp[i][w][0]
                dp[i+1][w][1] = dp[i][w][1]
                dp[i+1][w][2] = dp[i][w][2]
    MAX_ABS = abs(dp[N][W][0])+abs(dp[N][W][1])+abs(dp[N][W][2])
    if MAX_ABS > ans: ans = MAX_ABS
    #print(MAX_ABS,FGO,dp)

print(ans)

### FIXED CODE ###

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

L = []
for i in range(N):
    L.append(list(map(int,input().split())))
    
MAX_ANS = 0
for fgo in range(0,8):
    FGO = [pow(-1,fgo%2),pow(-1,(fgo//2)%2),pow(-1,(fgo//4)%2)]
    L = sorted(L,key=lambda x:x[0]*FGO[0]+x[1]*FGO[1]+x[2]*FGO[2],reverse=True)
    ans = 0
    for m in L[:W]:
        ans += m[0]*FGO[0] + m[1]*FGO[1] + m[2]*FGO[2]
    if ans > MAX_ANS: MAX_ANS = ans

print(MAX_ANS)
### BUGGY CODE ###

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

ans = round(n*(n-1)*(n-2)/6)

l.sort()

for i in range(n):
    for j in range(n):
        if i<=j:
            break
        for k in range(n):
            if l[i]+l[j]<=l[n-k-1]:
                ans-=1
            else:
                break

if ans<0:
    ans=0

print(ans)

### FIXED CODE ###

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

li.sort()
ans = 0

for i in range(n-2):
    for j in range(i+1,n-1):
        ans += bisect.bisect_left(li, li[i]+li[j]) - j - 1

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

from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
g = [[] for i in range(n)]
l = [0] * (n-1)
for _ in range(n-1):
  a,b = map(int,input().split())
  a,b = a-1,b-1
  l[_] = (min(a,b),max(a,b))
  g[a].append(b)
  g[b].append(a)
m = 0
for _ in range(n):
  m = max(m,len(g[_]))
  mi = _
print(m)
g2 = [set(range(1,m+1)) for i in range(n)]
deq = deque([mi])
vi = [0] * n
vi[mi] = 1
d = dict()
while deq:
  cur = deq.popleft()
  for i in g[cur]:
    if vi[i] == 1:
      continue
    else:
      vi[i] = 1
      deq.append(i)
      cu = (g2[cur]&g2[i]).pop()
      g2[cur].discard(cu)
      g2[i].discard(cu)
      d[(min(cur,i),max(cur,i))] = cu
for i in l:
  print(d[i])

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
g = [[] for i in range(n)]
l = [0] * (n-1)
for _ in range(n-1):
  a,b = map(int,input().split())
  a,b = a-1,b-1
  l[_] = (min(a,b),max(a,b))
  g[a].append(b)
  g[b].append(a)
m = 0
for _ in range(n):
  if len(g[_]) > m:
    m = len(g[_])
    mi = _
print(m)
g2 = [[] for i in range(n)]
stack = [(mi,-1)]
vi = [0] * n
vi[mi] = 1
d = dict()
while stack:
  pre,prei = stack.pop()
  c = 0
  for i in g[pre]:
    if vi[i] == 1:
      continue
    else:
      vi[i] = 1
      c += 1
      if c == prei:
        c += 1
      d[(min(pre,i),max(pre,i))] = c
      stack.append((i,c))
for i in l:
  print(d[i])
### BUGGY CODE ###

import math

def factorial(n):
    total = 1
    for i in range(1, n+1):
        total *= i
    return total

def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

MOD = 1000000000 + 7
def main():
    N, K = list(map(int, input().split()))

    for k in range(1, K+1):
        res = combinations_count(N-K+1, k)
        res *= combinations_count(K-1, k-1)
        print(res % MOD)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p


p = 10 ** 9 + 7
N = 2000  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)


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

for k in range(1, K + 1):
    res = cmb(N - K + 1, k, p)
    res *= cmb(K - 1, k - 1, p)
    print(res % p)
### BUGGY CODE ###

def main():
    s = input()
    t = input()
    sdash = s * 2
    ans = 0
    for i in t:
        if not i in s:
            print(-1)
            return
        index = sdash.index(i) + 1
        ans += index
        sdash = sdash[index:] + sdash[:index]
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    s = input()
    t = input()
    s2 = s * 2
    sett = list(set((t)))
    settindex = {}
    for i in sett:
        settindex[i] = sett.index(i)
        if i not in s:
            print(-1)
            return
    lens = len(s)
    # index[i文字目以降][settのindex]に何文字目にあるかが格納される
    index = [[-1] * len(sett) for _ in range(lens)]
    ans = 0
    n = 0
    for i in t:
        j = settindex[i]
        if index[n][j] == -1:
            index[n][j] = s2[n:].index(i)
        ans += index[n][j] + 1
        n += index[n][j] + 1
        n %= lens
    print(ans)


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

#!/usr/bin/env python3
import math

primes = [-1 for i in range(100000)]

def is_prime(x):
    global primes

    if primes[x] != -1:
        return primes[x] == 1

    if x < 2:
        primes[x] = 0
        return False
    if x == 2 or x == 3 or x == 5:
        primes[x] = 1
        return True
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0:
        primes[x] = 0
        return False

    sx = math.sqrt(x)
    prime = 7
    step = 4
    while prime <= sx:
        if x % prime == 0:
            primes[x] = 0
            return False

        prime += step
        step = 6 - step

    primes[x] = 1
    return True

def main():
    Q = int(input())
    l = []
    r = []
    for i in range(Q):
        sa = input().split(' ')
        l.append(int(sa[0]))
        r.append(int(sa[1]))

#    r_max = 100000
#    primes = [True for i in range(r_max)]
#    primes[0] = False
#    primes[1] = False
#    i = 2
#    max_i = int(math.sqrt(r_max))
#    while i <= max_i:
#        for j in range(i * i, r_max, i):
#            primes[j] = False
#        while i <= max_i:
#            i += 1
#            if primes[i]:
#                break

    for i in range(Q):
        c = 0
        for j in range(l[i], r[i] + 1, 2):
            if is_prime(j) and is_prime(int((j + 1) / 2)):
                c += 1
        print(c)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import math

def main():
    Q = int(input())
    l = []
    r = []
    for i in range(Q):
        na = list(map(int, input().split()))
        l.append(na[0])
        r.append(na[1])

    r_max = 100000
    primes = [True for i in range(r_max)]
    like_numbers = [0 for i in range(r_max)]

    primes[0] = primes[1] = False
    max_i = int(math.sqrt(r_max))
    i = 2
    while i <= max_i:
        primes[i] = True
        for j in range(i * i, r_max, i):
            primes[j] = False
        while i <= max_i:
            i += 1
            if primes[i]:
                break

    for i in range(3, r_max, 2):
        if primes[i] and primes[int((i + 1) / 2)]:
            like_numbers[i] = 1

    c = 0
    for i in range(3, r_max, 2):
        if like_numbers[i]:
            c += 1
        like_numbers[i] = c


    for i in range(Q):
        if l[i] == 1:
            print(like_numbers[r[i]])
        else:
            print(like_numbers[r[i]] - like_numbers[l[i] - 2])

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

N = int(input())
H = [int(s) for s in input().split()]
l=0
for i in range(N):
  t_l=0
  for j in range(i, N-1):
    if H[j] >= H[j+1]:
      t_l = t_l + 1
    else:
      break
  if l < t_l:
    l = t_l
  i=i+t_l
print(l)


### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
l=0
t_l = 0
for i in range(N-1):
  if H[i] >= H[i+1]:
    t_l = t_l + 1
    if l < t_l:
      l = t_l
  else:
    t_l=0
print(l)
### BUGGY CODE ###

k,s = map(int,input().split())
ans = 0
for i in range(k+1):
    for j in range(k+1):
        for l in range(k+1):
            if i+j+l == s:
                ans += 1
print(ans)

### FIXED CODE ###

k,s = map(int,input().split())
ans = 0
for i in range(k+1):
    for j in range(k+1):
        dum = (s - (i + j))
        if dum < 0:
            continue
        if dum <= k:
            ans += 1
print(ans)
### BUGGY CODE ###

*S, = map(ord, input())
*T, = map(ord, input())
LS = len(S); LT = len(T)

dp = [[-1]*(LT+1) for i in range(LS+1)]
nxt = [[(0, None, None)]*(LT+1) for i in range(LS+1)]
P = [[None]*(LT+1) for i in range(LS+1)]
Q = [[None]*(LT+1) for i in range(LS+1)]
R = [[0]*(LT+1) for i in range(LS+1)]
for i in range(LS-1, -1, -1):
    for j in range(LT-1, -1, -1):
        r0 = dp[i+1][j]; r1 = dp[i][j+1]
        r = max(r0, r1)
        if r0 < r1:
            rr = 0; p0 = i; q0 = j+1
        else:
            rr = 0; p0 = i+1; q0 = j
        if S[i] == T[j]:
            r2 = dp[i+1][j+1] + 1
            if r < r2:
                r = r2
                rr = 1; p0 = i+1; q0 = j+1
        dp[i][j] = r
        R[i][j] = rr
        P[i][j] = p0; Q[i][j] = q0

i = j = 0
ans = []
while i is not None:
    if R[i][j]:
        ans.append(S[i])
    i, j = P[i][j], Q[i][j]
print(*map(chr, ans), sep='')

### FIXED CODE ###

*S, = map(ord, input())
*T, = map(ord, input())
LS = len(S); LT = len(T)

dp = [[-1]*(LT+1) for i in range(LS+1)]
for i in range(LS-1, -1, -1):
    for j in range(LT-1, -1, -1):
        if S[i] == T[j]:
            dp[i][j] = max(dp[i+1][j+1] + 1, dp[i+1][j], dp[i][j+1])
        else:
            dp[i][j] = max(dp[i+1][j], dp[i][j+1])
i = j = 0
ans = []
while i < LS and j < LT:
    if S[i] == T[j]:
        if dp[i][j] == dp[i+1][j+1] + 1:
            ans.append(S[i])
            i += 1; j += 1
        elif dp[i][j] == dp[i+1][j]:
            i += 1
        else:
            j += 1
    else:
        if dp[i][j] == dp[i+1][j]:
            i += 1
        else:
            j += 1
print(*map(chr, ans), sep='')