Harryxun/stf_run huggingface dataset:
N,K = map(int, input().split())
A = list(map(int, input().split()))

dp = [[0] * (K+10) for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
    for j in range(K,0,-1):
        dp[i+1][j] += dp[i][j]
        dp[i+1][j] %= MOD
        if j + a[i] + 1 <= K+1:
            dp[i+1][j+a[i]+1] = (dp[i+1][j+a[i]+1] - dp[i][j] + MOD) % MOD
    
    for j in range(K+1):
        dp[i+1][j+1] += dp[i+1][j]
        dp[i+1][j+1] %= MOD

print(dp[N][K])


### FIXED CODE ###

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

dp = [[0] * (K+10) for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
    for j in range(K,-1,-1):
        dp[i+1][j] += dp[i][j]
        dp[i+1][j] %= MOD
        if j + A[i] + 1 <= K+1:
            dp[i+1][j+A[i]+1] = (dp[i+1][j+A[i]+1] - dp[i][j] + MOD) % MOD
    
    for j in range(K+1):
        dp[i+1][j+1] += dp[i+1][j]
        dp[i+1][j+1] %= MOD

print(dp[N][K])
from collections import defaultdict, deque
n,m = list(map(int, input().split()))

d = defaultdict(list)

for _ in range(m):
    
    a,b = list(map(int, input().split()))
    d[a].append(b)
    d[b].append(a)
    
   
def dfs(node):
    
    s = set()
    stack = deque([node])
    while stack:
        
        n = stack.popleft()
        s.add(n)
        for i in d[n]:
            if i not in s and visited[i] == 0:
                stack.append(i)
                
    return s
    

keys = list(d.keys())
m = max(keys)
visited = [0]*(2*10**5+1)
ans = 0
for key in keys:
    if visited[key] == 0:
        ans +=1
        s = dfs(key)
        for i in range(key, m+1):
            if visited[i] == 0 and i not in s:
                visited[i] = 1


print(ans)
        

### FIXED CODE ###

from collections import defaultdict, deque
n,m = list(map(int, input().split()))

d = defaultdict(set)

for _ in range(m):
    
    a,b = list(map(int, input().split()))
    d[a].add(b)
    d[b].add(a)
    
visited = set()

def dfs(node):
    
    c = 0
    stack = deque([node])
    visited.add(node)
    while stack:
        n = stack.popleft()
        c+=1
        for i in d[n]:
            if  i not in visited:
                visited.add(i)
                stack.append(i)
                
    return c
    

ans = 1

for key in list(d.keys()):
    if key not in visited:

        c = dfs(key)
        ans = max(ans, c)
        


print(ans)
from collections import defaultdict
from fractions import Fraction
def powmod(x, n,mod):
  if n == 0:
   return 1
  K = 1
  while n > 1:
   if n % 2 != 0:
    K = K * x%mod
    x = x ** 2%mod
    n = (n - 1) // 2
   else:
    x = x ** 2%mod
    n = n // 2%mod

  return K * x # 指数を割り続け n が 1 に至ったら終了
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 range(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 k>0:
   dic[Fraction(A,B)][0]+=1
  else:
   dic[-1/Fraction(A,B)][1]+=1
ans=1
for k in dic:
 ans*=(powmod(2,dic[k][0],mod)+powmod(2,dic[k][1],mod) -1)
 ans%=mod
ans*=(powmod(2,c,mod)+powmod(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)
import bisect
import sys
sys.setrecursionlimit(10**9)
n = int(input())
a = [0]+list(map(int,input().split()))
tree = [[] for _ in range(n+1)]
for _ in range(n-1):
  u,v = map(int,input().split())
  tree[u].append(v)
  tree[v].append(u)
#print(tree)
d = [float("inf")]*(n+1)
ans = [0]*(n+1)

def dfs(now, pre):
  print(now,pre)
  i = bisect.bisect_left(d, a[now])
  tmp = d[i]
  d[i] = a[now]
  ans[now] = bisect.bisect_left(d, float("inf"))
  print(d)
  for nxt in tree[now]:
    if nxt == pre:
      continue
    dfs(nxt, now)
  d[i] = tmp
dfs(1,-1)

for i in ans[1:]:
  print(i)

### FIXED CODE ###

import bisect
import sys
sys.setrecursionlimit(10**9)
n = int(input())
a = [0]+list(map(int,input().split()))
tree = [[] for _ in range(n+1)]
for _ in range(n-1):
  u,v = map(int,input().split())
  tree[u].append(v)
  tree[v].append(u)
#print(tree)
d = [float("inf")]*(n+1)
ans = [0]*(n+1)

def dfs(now, pre):
  i = bisect.bisect_left(d, a[now])
  tmp = d[i]
  d[i] = a[now]
  ans[now] = bisect.bisect_left(d, float("inf"))
  for nxt in tree[now]:
    if nxt == pre:
      continue
    dfs(nxt, now)
  d[i] = tmp
dfs(1,-1)

for i in ans[1:]:
  print(i)
n, m = map(int, input().split())
a = [0 for _ in range(n+1)]
for i in range(m):
    a[int(input())] = 1

dp = [-1 for _ in range(n+1)]
dp[-1], dp[-2], dp[-3] = 0, 1, 2

for i in range(n-3, -1, -1):
    if a[i] == 1:
        dp[i] = 0
    else:
        dp[i] = dp[i+1] +dp[i+2]
print(dp[0]%1000000007)


### FIXED CODE ###

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

# i段目が壊れているならa[i] = 1,そうでないならa[i] = 0
a = [0 for _ in range(n+1)]
for i in IN:
    a[i] = 1

# dp[i] := i段目から最上段にたどり着くまでの移動方法の数
# dp[i] = 0 (a[i] が 1)
# dp[i] = dp[i+1] + dp[i+2] (それ以外)
dp = [-1 for _ in range(n+1)]

dp[n] = 0
if a[n-1] == 1:
    dp[n-1] = 0
else:
    dp[n-1] = 1
if a[n-2] == 1:
    dp[n-2] = 0
elif dp[n-1] == 0:
    dp[n-2] = 1
else:
    dp[n-2] = 2

for i in range(n-3, -1, -1):
    if a[i] == 1:
        dp[i] = 0
    else:
        dp[i] = dp[i+1] +dp[i+2]

print(dp[0]%(10 ** 9 + 7))
def main():
    s = input()
    ans = 0
    for i in range((len(s) - 1) ** 2):
        tmp = ""
        for j in range(len(s)):
            tmp += s[j]
            if (i >> j) & 1:
                tmp += "+"
        else:
            ans += eval(tmp)
    else:
        print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    s = input()
    ans = 0
    for i in range(2 ** (len(s) - 1)):
        tmp = ""
        for j in range(len(s)):
            tmp += s[j]
            if(j < len(s) - 1):
                if (i >> j) & 1:
                    tmp += "+"
        else:
            #print("i =", i, " ", ans, "+", tmp, "=", end = "")
            ans += eval(tmp)
    else:
        print(ans)

if __name__ == "__main__":
    main()
N=int(input())
S=list(input())
count=0
for i in range(N):
  if S[i]=="A":
    if S[i+1]=="B":
      if S[i+2]=="C":
        count+=1
print(count)
    

### FIXED CODE ###

N=int(input())
S=list(input())
count=0
for i in range(N-2):
  if S[i]=="A":
    if S[i+1]=="B":
      if S[i+2]=="C":
        count+=1
print(count)
import math
n = int(input())
t = map(int, input())
bottle_neck = min(t)[0]
ti = math.ceil(n/bottle_neck)
print(ti+4)


### FIXED CODE ###

import math
n = int(input())
t=[]
for i in range(5):
    t.append(int(input()))
bottle_neck = min(t)
ti = math.ceil(n/bottle_neck)
print(ti + 4)
n,a,b=map(int,input().split()
if n*a >= b:
  print(b)
else:
  print(n*a)

### FIXED CODE ###

n,a,b=map(int,input().split())
if n*a >= b:
  print(b)
else:
  print(n*a)
from itertools import permutations

def input_list() :
    return list(map(int, input().split()))

n, m ,r = input_list()
road = input_list()
road = [x-1 for x in road]
d = [[float('inf')] * n for i in range(n)]
for i in range(n) :
    d[i][i] = 0
for i in range(m) :
    a, b, c = input_list()
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c

for k in range(n) :
    for i in range(n) :
        for j in range(n) :
            dist = d[i][k]+d[k][j]
            if d[i][j] > dist
            d[i][j] = dist

ans = float('inf')
for p in permutations(road) :
    dist = 0
    for i in range(r-1) :
        dist += d[p[i]][p[i+1]]
    if ans > dist :
        ans = dist

print(ans)

### FIXED CODE ###

from itertools import permutations

def input_list() :
    return list(map(int, input().split()))

def main() :
    n, m ,r = input_list()
    road = input_list()
    road = [x-1 for x in road]
    d = [[float('inf')] * n for i in range(n)]
    for i in range(n) :
        d[i][i] = 0
    for i in range(m) :
        a, b, c = input_list()
        a -= 1
        b -= 1
        d[a][b] = c
        d[b][a] = c

    for k in range(n) :
        for i in range(n) :
            for j in range(n) :
                dist = d[i][k]+d[k][j]
                if d[i][j] > dist :
                    d[i][j] = dist

    ans = float('inf')
    for p in permutations(road) :
        dist = 0
        for i in range(r-1) :
            dist += d[p[i]][p[i+1]]
        if ans > dist :
            ans = dist

    print(ans)

main()
n,k=map(int,input().split())
a=[0]+[int(input())-k for i in range(n)]
for i in range(1,n+1):
	a[i]+=a[i-1]
b=sorted(a)+[-2e9-1]
c,d=0,dict()
for i in range(n+1):
	if b[i]!=b[i-1]:
		c+=1
		d[b[i]]=c
bit=[0]*(n+1)
def sum(i):
	res=0
	while i>0:
		res+=bit[i]
		i-=i&-i
	return res
def add(i):
	while i<=c:
		bit[i]+=1
		i+=i&-i
ans=0
for i in range(n+1):
	ans+=sum(d[a[i]])
	add(d[a[i]])
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
a=[0]+[int(input())-k for i in range(n)]
for i in range(1,n+1):
	a[i]+=a[i-1]
b=sorted(a)+[-2e9-1]
c,d=0,dict()
for i in range(n+1):
	if b[i]!=b[i-1]:
		c+=1
		d[b[i]]=c
bit=[0]*(n+5)
def sum(i):
	res=0
	while i>0:
		res+=bit[i]
		i-=i&-i
	return res
def add(i):
	while i<=c:
		bit[i]+=1
		i+=i&-i
ans=0
for i in range(n+1):
	ans+=sum(d[a[i]])
	add(d[a[i]])
print(ans)
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;

int main(){
  //入力
  int A, B, C;
  cin >> A >> B >> C;

  //処理
  int ans = B / A;
  if (ans > C) ans = C;

  //出力
  cout << ans << endl;
}


### FIXED CODE ###

int_list = input().strip().split()

fee_per_sound = int(int_list[0])
takahasi_money = int(int_list[1])
satisfaction_number = int(int_list[2])

if takahasi_money >= fee_per_sound*satisfaction_number:
    print(satisfaction_number)
else:
    print(takahasi_money//fee_per_sound)
print(list(input()).count('1'))	]


### FIXED CODE ###

print(list(input()).count('1'))
n=int(input())
if n==3:
  print(2,5,63)
elif n==4:
  print(2,5,20,63)
elif n==5:
  print(2,5,20,30,63)
else:
  l=[2,3]
  cnt=2
  last=0
  for i in range(6,30001):
    if i%6 in [0,2,3,4]:
      l.append(i)
      cnt+=1
      if cnt==n:
        last=i
        break
  m=sum(l)
  if m%6==2:
    l.remove(8)
    for i in range(6):
      if (last+i)%6==0:
        l.append(last+i)
        break
  elif m%6==3:
    l.remove(9)
    for i in range(6):
      if (last+i)%6==0:
        l.append(last+i)
        break
  elif m%6==5:
    l.remove(9)
    for i in range(6):
      if (last+i)%6==4:
        l.append(last+i)
        break
print(*l)

### FIXED CODE ###

n=int(input())
if n==3:
  print(2,5,63)
elif n==4:
  print(2,5,20,63)
elif n==5:
  print(2,5,20,30,63)
else:
  l=set()
  cnt=0
  e=0
  for i in range(2,30001):
    if i%2==0 or i%3==0:
      l.add(i)
      cnt+=1
      if cnt==n:
        m=sum(l)
        if m%6==2:
          l.discard(8)
          l.add((i//6+1)*6)
        elif m%6==3:
          l.discard(9)
          l.add((i//6+1)*6)
        elif m%6==5:
          l.discard(8)
          l.add((i+3)//6*6+3)
        break
  print(' '.join(map(str,l)))
if __name__ == '__main__':
    [N, C, K] = [int(i) for i in input().split()]

    T = []
    for i in range(K):
        T.append(int(input()))
    T.sort()

    counter = 1

    num_people = 0

    flag = False

    for num in T:
        print(num)
        print(flag)
        num_people += 1
        if flag:
            if num - first_time <= K and num_people <= C:
                continue
            else:
                counter += 1
                num_people = 1
                flag = False
                print('inc')
        else:
            first_time = num
            flag = True
        

    print(counter)


### FIXED CODE ###

if __name__ == '__main__':
    [N, C, K] = [int(i) for i in input().split()]

    T = []
    for i in range(N):
        T.append(int(input()))
    T.sort()

    counter = 1

    num_people = 0

    flag = False

    for num in T:
        num_people += 1
        if flag:
            if num - first_time <= K and num_people <= C:
                continue
            else:
                counter += 1
                num_people = 1
                first_time = num

        else:
            first_time = num
            flag = True

    print(counter)
N, M = map(int, input().split())
Alist = list(map(int, input().split()))

def solve(A, M):
    if len(A) > 1:
        if M==1:
            B = sum(A[1:]) + A[0]//2
        else:
            A = [A[0]//2] + A[1:]
            A.sort(reverse=True)
            B = solve(A, M-1)
    else:
        B = A[0] // (2**M)
    return B

Alist.sort(reverse=True)
B = solve(Alist, M)
print(B)

### FIXED CODE ###

import heapq
N, M = map(int, input().split())
Alist = list(map(int, input().split()))

q = []
for a in Alist:
    heapq.heappush(q, -a)

for i in range(M):
    m = heapq.heappop(q)
    heapq.heappush(q, -((-m)//2))

print(-sum(q))
# coding: utf-8
# Your code here!
MOD = 10**9+7
import math
import sys

sys.setrecursionlimit(100000)
n,m=[int(i) for i in input().split()]

yaku = set()
for i in range(1,math.floor(math.sqrt(m+1))+2):
    if m%i ==0:
        yaku.add(i)

cc=[]
for i in yaku:
    cc.append(m//i)
for i in cc:
    yaku.add(i)

memo = {}
def func(p,q):
    c=0
    if q==1:
        return 1
    for i in yaku:
        if p%i != 0:
            continue
        if (p//i,q-1) not in memo:
            k=func(p//i,q-1)%MOD
            c+=k%MOD
            memo[(p//i,q-1)]=k
        else: 
            c+= memo[(p//i,q-1)] % MOD
    return c
        
    
#print(yaku)
print(func(m,n))
#print(memo)





### FIXED CODE ###

# coding: utf-8
# Your code here!
def prime_factorize(N): #素因数分解
    exponent = 0
    while N%2 == 0:
        exponent += 1
        N //= 2
    if exponent: factorization = [[2,exponent]]
    else: factorization = []
    i=1
    while i*i <=N:
        i += 2
        if N%i: continue
        exponent = 0
        while N%i == 0:
            exponent += 1
            N //= i
        factorization.append([i,exponent])
    if N!= 1: factorization.append([N,1])
    assert N != 0, "zero"
    return factorization

SIZE=110000; MOD=10**9+7 #998244353 #ここを変更する

SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
fac = [0]*SIZE  # fac[j] = j! mod MOD
finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
    inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD

def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

#n = int(input())
#n,a = [int(i) for i in readline().split()]
n,m = [int(i) for i in readline().split()]

MOD = 10**9+7

ans = 1
L = prime_factorize(m)
for p,e in L:
    ans *= choose(n-1+e,e)
    ans %= MOD


print(ans)
from collections import deque
h,w=map(int,input().split())
maze=[['#' for i in range(w+2)]]+[['#']+[x=='#' for x in input()]+['#'] for i in range(h)]+[['#' for i in range(w+2)]]
f=0
for i in range(1,h+1):
  for j in range(1,w+1):
    if maze[i][j]:
	    f+=1

pos=deque([(1,1,0)])
while pos:
    x,y,c=pos.popleft()
    if (x,y)==(h,w):
        z=c
        break
    elif maze[x][y]:
        continue    
    pos.append((x-1, y, c+1))
    pos.append((x+1, y, c+1))
    pos.append((x, y-1, c+1))
    pos.append((x, y+1, c+1))
    maze[x][y] = True
    
print(h*w-f-z-1)

### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
maze=[['#' for i in range(w+2)]]+[['#']+[x=='#' for x in input()]+['#'] for i in range(h)]+[['#' for i in range(w+2)]]
f=0
for i in range(1,h+1):
  for j in range(1,w+1):
    if maze[i][j]:
	    f+=1
z=0
pos=deque([(1,1,0)])
while pos:
    x,y,c=pos.popleft()
    if (x,y)==(h,w):
        print(h*w-f-c-1)
        z=1
        break
    elif maze[x][y]:
        continue
    pos.append((x-1, y, c+1))
    pos.append((x+1, y, c+1))
    pos.append((x, y-1, c+1))
    pos.append((x, y+1, c+1))
    maze[x][y] = True
if z==0:
	print(-1)
days = ['SUN', 'MON', 'TUE', 'WED', 'THU',' FRI', 'SAT']
S = input()
print(7 - days.index(S))

### FIXED CODE ###

days = ['SUN', 'MON', 'TUE', 'WED', 'THU', 'FRI', 'SAT']
S = input()
print(7 - days.index(S))
from math import factorial


n = int(input())
a = [sorted(input()) for i in range(n)]

l = []
count = 0
for i in range(n):
    if a[i] not in l:
        m = a.count(a[i])
        if m > 1:
            count += factorial(m) / 2 / factorial(m - 2)
        l.append(a[i])
    else:
        pass
print(int(count))
    


### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]

count = 0
dic1 = {}
#print(s)
for i in range(n):
    #print(s[i])
    so = sorted(s[i])
    so = ''.join(so)
    if so in dic1:
        count += dic1[so]
        dic1[so] += 1
    else:
        dic1[so] = 1
    #print(count, dic1)
print(count)
n, m = map(int, input().split())
list_score = []
for _ in range(m):
    list_score.append(int(input()))

dp = [0] * (n + 1)
mod = pow(10, 9) + 7

dp[0] = 1
list_score.sort()
if list_score[0] == 1:
    dp[1] = 0
else:
    dp[1] = 1

for i in range(2, n + 1):
    if i not in list_score:
        dp[i] = dp[i - 1] + dp[i - 2]
        dp[i] %= mod

print(dp[n])

### FIXED CODE ###

N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])
INF = 1000000007

dp = [0] * (N + 1)
dp[0] = 1
if 1 not in a:
	dp[1] = 1
else:
	dp[1] = 0
for i in range(2, N + 1):
	if i in a:
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
	dp[i] %= INF

print(dp[N])
N, X_MAX=input().split()
L = input().split()
i = 0
X = 0

while int(X_MAX) >= X:
    X += int(L[i])
    i+=1
print(i)

### FIXED CODE ###

N, X_MAX=input().split()
L = input().split()
count_i = 1
X = 0

for L_n in L:
    X += int(L_n)
    if int(X_MAX) < X:
        break
    count_i += 1
print(count_i)
import numpy as np
n = int(input())
rs = [list(map(int, input().split())) for _ in range(n)]
rs = np.array(rs)
mn_mx = np.stack([rs[:, 0] - rs[:, 1], rs[:, 0] + rs[:, 1]], axis=1)
mn_mx = mn_mx[np.argsort(mn_mx[:, 1])]

cnt = 0
reach = None
for mn, mx in mn_mx:
    if reach is not None and mn < reach:
        continue
    reach = mx
    cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
rs = [list(map(int, input().split())) for _ in range(n)]
lr = [[x-l, x+l] for x, l in rs]
lr.sort(key=lambda x: x[1])

cnt = 0
reach = None
for l, r in lr:
    if reach is not None and l < reach:
        continue
    reach = r
    cnt += 1
print(cnt)
from scipy.sparse.csgraph import csgraph_from_dense,floyd_warshall

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

A=[[10**12 for i in range(N+1)]for j in range(N+1)]
B=[[10**12 for i in range(N+1)]for j in range(N+1)]
for i in range(M):
    a,b,c=map(int,input().split())
    if c<=L:
        A[a][b]=c
        A[b][a]=c
        B[a][b]=1
        B[b][a]=1

#print(A)

AG = csgraph_from_dense(A)
A=floyd_warshall(AG)
#print(A)
for i in range(N+1):
    for j in range(N+1):
        if A[i][j]<=L:
            B[i][j]=1
"""for c in range(1,N+1):
    for a in range(1,N+1):
        for b in range(1,N+1):
            A[a][b]=min(A[a][b],A[a][c]+A[c][b])
            if A[a][b]<=L:
                B[a][b]=1"""
#print(B)
BG=csgraph_from_dense(B)
B=floyd_warshall(BG)
"""for c in range(1,N+1):
    for a in range(1,N+1):
        for b in range(1,N+1):
            B[a][b]=min(B[a][b],B[a][c]+B[c][b])"""

#print(B)
Q=int(input())
for i in range(Q):
    s,t=map(int,input().split())
    if B[s][t]==10**12:
        print(-1)
    else:
        print(int(B[s][t]-1))

### FIXED CODE ###

from scipy.sparse.csgraph import floyd_warshall

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

A=[[10**12 for i in range(N+1)]for j in range(N+1)]
B=[[10**12 for i in range(N+1)]for j in range(N+1)]
for i in range(M):
    a,b,c=map(int,input().split())
    if c<=L:
        A[a][b]=c
        A[b][a]=c
        B[a][b]=1
        B[b][a]=1

#print(A)


A= floyd_warshall(A,directed = False)
#print(A)
for i in range(N+1):
    for j in range(N+1):
        if A[i][j]<=L:
            B[i][j]=1
"""for c in range(1,N+1):
    for a in range(1,N+1):
        for b in range(1,N+1):
            A[a][b]=min(A[a][b],A[a][c]+A[c][b])
            if A[a][b]<=L:
                B[a][b]=1"""
#print(B)

B= floyd_warshall(B,directed = False)
"""for c in range(1,N+1):
    for a in range(1,N+1):
        for b in range(1,N+1):
            B[a][b]=min(B[a][b],B[a][c]+B[c][b])"""

#print(B)
Q=int(input())
for i in range(Q):
    s,t=map(int,input().split())
    if B[s][t]==10**12:
        print(-1)
    else:
        print(int(B[s][t]-1))
import sys
import copy
from collections import deque
stdin = sys.stdin
 
mod = 10**9+7
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces
 
n = ni()
a = na()
a.sort()
a_max = max(a)

c = [0 for _ in range(1000000)]
for aa in a:
    c[aa] += 1

dp = [False for _ in range(1000000)]
cnt = 0
for ai in set(a):
    if dp[ai]:
        continue
    if c[ai]==1:
        cnt += 1
    for j in range(ai+ai, a_max+1, ai):
        dp[j] = True

print(cnt)

### FIXED CODE ###

import sys
import copy
from collections import deque
stdin = sys.stdin
 
mod = 10**9+7
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces
 
n = ni()
a = na()
a.sort()
a_max = max(a)

c = [0 for _ in range(1000005)]
for aa in a:
    c[aa] += 1

dp = [False for _ in range(1000005)]
cnt = 0
for ai in set(a):
    if dp[ai]:
        continue
    if c[ai]==1:
        cnt += 1
    for j in range(ai+ai, a_max+1, ai):
        dp[j] = True

print(cnt)
from sys import setrecursionlimit
setrecursionlimit(100000)
   
class Node():
    NIL = -1

    def __init__(self, parent=NIL, left=NIL, right=NIL, depth=-1):
        self.parent = parent
        self.left = left
        self.right = right
        self.depth = depth

def read_nodes(T):
    for _ in range(len(T)):
        id, _, *child = [int(x) for x in input().split()]
        for i, c in enumerate(child):
            if i == 0:
                T[id].left = c
            else:
                T[l].right = c
            l = c
            T[c].parent = id

def calc_depth(T):

    def rec(r, p):
        nonlocal T

        T[r].depth = p
        if T[r].right != Node.NIL:
            rec(T[r].right, p)
        if T[r].left != Node.NIL:
            rec(T[r].left, p + 1)

    rec([u.parent for u in T].index(-1), 0)

def node_type(T, id):
    if T[id].parent == Node.NIL:
        return "root"
    elif T[id].left == Node.NIL:
        return "leaf"
    else:
        return "internal node"

def child(T, id):
    c = []
    i = T[id].left
    while i != Node.NIL:
        c.append(i)
        i = T[i].right
    return c

def print_nodes(T):
    for id in range(len(T)):
        print("node {}: parent = {}, depth = {}, {}, {}".
              format(id, T[id].parent, T[id].depth,
                     node_type(T, id), child(T, id)))

def main():
    n = int(input())
    T = [Node() for _ in range(n)]

    read_nodes(T)
    calc_depth(T)
    print_nodes(T)

main()


### FIXED CODE ###

class Node():
    def __init__(self, parent=-1, child=[]):
        self.parent = parent
        self.child = child


def node_depth(u, id):
    if u[id].parent == -1:
        return 0
    else:
        return node_depth(u, u[id].parent) + 1


def node_type(u, id):
    if u[id].parent == -1:
        return "root"
    elif u[id].child == []:
        return "leaf"
    else:
        return "internal node"


def main():
    n = int(input())
    u = [Node() for _ in range(n)]

    for _ in range(n):
        id, _, *child = (int(x) for x in input().split())
        u[id].child = child
        for c in child:
            u[c].parent = id

    for id in range(n):
        print("node {}: parent = {}, depth = {}, {}, {}".
              format(id, u[id].parent,
                     node_depth(u, id), node_type(u, id),
                     u[id].child))


main()