Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import math
A, B = map(int, input().split())

def gcd(A, B):
  if A < B:
    A, B = B, A
  while B > 0:
    temp = A % B
    A = B
    B = temp
  return A

gcd_num = gcd(A, B)

def prime(a):
  max_a = int(math.sqrt(a))
  d = dict()
  d[1] = 1
  i = 2
  while a != 1:
    if a % i == 0:
      a = a // i
      if i in d:
        d[i] += 1
      else:
        d[i] = 1
    else:
      i += 1
  return d
d = prime(gcd_num) 

print(len(d))

Fixed submission:
import math
A, B = map(int, input().split())

def gcd(A, B):
  if A < B:
    A, B = B, A
  while B > 0:
    temp = A % B
    A = B
    B = temp
  return A

gcd_num = gcd(A, B)

def prime(a):
  max_a = 1 + int(math.sqrt(a))
  d = dict()
  d[1] = 1
  i = 2
  while a != 1:
    if i > max_a:
      d[a] = 1
      break
    if a % i == 0:
      a = a // i
      if i in d:
        d[i] += 1
      else:
        d[i] = 1
    else:
      i += 1
  return d
d = prime(gcd_num) 

print(len(d))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
ans = 0
for i in range(1,N):
  ans += i % (i+1)
print(ans)

Fixed submission:
N = int(input())
print(N*(N-1) // 2)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
D = list(map(int, input().split()))

def quicksort(a):
  if len(set(a)) < 2:
    return a
  left = []
  center = a.pop(0)
  right = []
  for i in a:
    if center > i:
      left.append(i)
    else:
      right.append(i)
  left = quicksort(left)
  right = quicksort(right)
  left.append(center)
  left.extend(right)
  return left

D = quicksort(D)

left = D[int((N/2)-1)]
right = D[int(N/2)]
ans = 0
if left < right:
  ans = right - left
print(ans)



Fixed submission:
N = int(input())
d = list(map(int, input().split()))
d.sort()
middle = (N // 2) -1
print(d[middle+1] - d[middle])
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
MOD = 10 ** 9 + 7
s = 0

def comb(n, k):
  if k > n - k:
    k = n - k
  de = 1
  nu = 1
  for i in range(k):
    de *= (n - i)
    de = de % MOD
    nu *= (i + 1)
    nu = nu % MOD
  nu = pow(nu, -1, MOD)
  return (de * nu) % MOD

ans = 1

for i in range(M):
  temp = 0
  l = int(input()) - 1
  if s > l:
    print(0)
    exit()
  step = l - s
  for j in range(1 + (step // 2)):
    temp += comb(step-j, j)
    temp = temp % MOD
  ans *= temp
  ans = ans % MOD
  s = l + 2
l = N
step = l - s
temp = 0
for i in range(1 + (step // 2)):
  temp += comb(step-i, i)
  temp = temp % MOD
ans *= temp
ans = ans % MOD

print(ans)

Fixed submission:
N, M = map(int, input().split())
MOD = 10 ** 9 + 7
s = 0

def comb(n, k):
  if k > n - k:
    k = n - k
  de = 1
  nu = 1
  for i in range(k):
    de *= (n - i)
    de = de % MOD
    nu *= (i + 1)
    nu = nu % MOD
  nu = pow(nu, -1, MOD)
  return (de * nu) % MOD

def calc_from_step(step):
  temp = 0
  for i in range(1 + (step // 2)):
    temp += comb(step-i, i)
  return temp


arr = [1, 1]
steps = []
step = 0
s = 0
for i in range(M):
  l = int(input()) - 1
  steps.append(l-s)
  if s > l:
    print(0)
    exit()
  if step < l - s:
    step = l - s
  s = l + 2
l = N
steps.append(l-s)
if step < l - s:
  step = l - s

for i in range(step - 1):
  arr.append((arr[i] + arr[i+1])%MOD)
ans = 1

for i in steps:
  ans *= arr[i]
  ans = ans % MOD
print(ans)
Buggy python submission (verdict: Runtime Error):
print(int(input)*2)

Fixed submission:
N = int(input())
if N % 2 == 0:
  print(N)
else:
  print(N*2)
Buggy python submission (verdict: Time Limit Exceeded):
a = int(input())
b = []
for i in range(len(str(a))):
    b.append(str(a)[i])
b = [int(j) for j in b]
if sum(b) % 9 == 0:
    print("Yes")
else:
    print("No")

Fixed submission:
a = str(input())
b = []
c = 0
for i in range(len(a)):
    b.append(int(a[i]))
if sum(b) % 9 == 0:
    print("Yes")
else:
    print("No")

Buggy python submission (verdict: Runtime Error):
[int(s) for s in l_si]

Fixed submission:
a = str(input())
b = []
c = 0
for i in range(len(a)):
    b.append(int(a[i]))
if sum(b) % 9 == 0:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Runtime Error):
print([1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51][int(input())])

Fixed submission:
a=[1,1,1,2,1,2,1,5,2,2,1,5,1,2,1,14,1,5,1,5,2,2,1,15,2,2,5,4,1,4,1,51]
print(a[int(input())-1])
Buggy python submission (verdict: Runtime Error):
a,b,c = input().split(' ')
for i in range(int(c)):
  if int(a) >= 1:
    a = int(a) - 1
  else:
    b = int(b) - 1
print(a + " " + b)

Fixed submission:
a,b,k = map(int , input().split())
if a < k:
    b = (a + b) - k
    if b < 0:
        b = 0
    a = 0
elif a >= k:
    a = a - k
print(a,b)
Buggy python submission (verdict: Runtime Error):
if a[0] == a[1] and a[1] == a[2]:
    print("Yes")
else:
    print("No")

Fixed submission:
a = input().split()
if a[0] == a[1] and a[1] == a[2]:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Runtime Error):
print(input().count())

Fixed submission:
print(input().count("2"))

Buggy python submission (verdict: Runtime Error):
a = input().split()
b = 0
for i in range(2):

    a.sort(reverse=True)
    print(a)
    b = b + int(a[1])
    a[1] = str(int(a[1]) - 1)
print(b)


Fixed submission:
print(input().count("2"))
Buggy python submission (verdict: Runtime Error):
if a == 22:
    print("Christmas Eve Eve Eve")
elif a == 23:
    print("Christmas Eve Eve")
elif a == 24:
    print("Christmas Eve")
elif a == 25:
    print("Christmas")

Fixed submission:
D = int(input())
if D == 22:
    print("Christmas Eve Eve Eve")
elif D == 23:
    print("Christmas Eve Eve")
elif D == 24:
    print("Christmas Eve")
elif D == 25:
    print("Christmas")

Buggy python submission (verdict: Runtime Error):
if a == "22":
    print("Christmas Eve Eve Eve")
elif a == "23":
    print("Christmas Eve Eve")
elif a == "24":
    print("Christmas Eve")
elif a == "25":
    print("Christmas")

Fixed submission:
D = int(input())
if D == 22:
    print("Christmas Eve Eve Eve")
elif D == 23:
    print("Christmas Eve Eve")
elif D == 24:
    print("Christmas Eve")
elif D == 25:
    print("Christmas")
Buggy python submission (verdict: Runtime Error):
if (a * b) % 2 == 1:
    print("Odd")
else:
    print("Even")

Fixed submission:
a,b = map(int,input().split())
if (a * b) % 2 == 1:
    print("Odd")
else:
    print("Even")
Buggy python submission (verdict: Runtime Error):
a,b=map(int,input().split())
if a + b >= 10:
    print("error")
else:
    print(a + b)

Fixed submission:
a,b,c=map(int,input().split())
if c >= a and c <= b:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


MOD = 10 ** 9 + 7


def main():
    N = II()
    target = LI()

    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            ans += (target[i] % MOD) * (target[j] % MOD) % MOD
            ans = ans % MOD
    print(ans)


main()


Fixed submission:
#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


MOD = 10 ** 9 + 7


def main():
    N = II()
    target = LI()

    ans = 0
    sums = [0] * N
    sum_all = target[0]
    sums[0] = target[0]
    for i in range(1, N):
        sum_all += target[i] % MOD
        sums[i] = sums[i-1] + target[i]

    for i in range(N):
        ans += target[i] * (sum_all - sums[i])
        ans = ans % MOD

    print(ans)


main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()
    target = LI()

    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            ans += (target[i] * target[j]) % (10 ** 9 + 7)
            ans = ans % (10 ** 9 + 7)
    print(ans)


main()


Fixed submission:
#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


MOD = 10 ** 9 + 7


def main():
    N = II()
    target = LI()

    ans = 0
    sums = [0] * N
    sum_all = target[0]
    sums[0] = target[0]
    for i in range(1, N):
        sum_all += target[i] % MOD
        sums[i] = sums[i-1] + target[i]

    for i in range(N):
        ans += target[i] * (sum_all - sums[i])
        ans = ans % MOD

    print(ans)


main()
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()
    targets = LI()
    MAX_INT = max(targets) + 1
    targets = set(targets)
    is_pw = True

    if len(targets) != N:
        is_pw = False

    if len(targets) == 1:
        if targets[0] == 1:
            print("setwise coprime")
            return
        print("not coprime")
        return

    for i in range(2, MAX_INT):
        origin = i
        kosuu = 0
        while origin <= MAX_INT:
            if origin in targets:
                kosuu += 1
            origin += i

        if kosuu <= 1:
            continue
        elif kosuu < len(targets):
            is_pw = False
        else:
            print("not coprime")
            return

    if is_pw:
        print("pairwise coprime")
        return
    print("setwise coprime")


main()


Fixed submission:
#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()
    targets = LI()
    MAX_INT = max(targets) + 1
    counter = cl.Counter(targets)
    targets = set(targets)
    is_pw = True

    num_1 = counter[1]
    if num_1 > 1:
        N -= num_1 - 1

    if len(targets) != N:
        is_pw = False

    if len(targets) == 1:
        if 1 in targets:
            print("pairwise coprime")
            return
        print("not coprime")
        return

    for i in range(2, MAX_INT):
        origin = i
        kosuu = 0
        while origin <= MAX_INT:
            if origin in targets:
                kosuu += 1
            origin += i

        if kosuu <= 1:
            continue
        elif kosuu < len(targets):
            is_pw = False
        else:
            print("not coprime")
            return

    if is_pw:
        print("pairwise coprime")
        return
    print("setwise coprime")


main()
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    n, k = MI()
    scores = LI()

    score_now = 1

    for i in range(k):
        score_now *= scores[i]

    for i in range(k, n):
        next_score = score_now * (scores[i] / scores[i - k])
        print("Yes" if next_score > score_now else "No")


main()


Fixed submission:
#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    n, k = MI()
    scores = LI()

    score_now = 1

    for i in range(k, n):
        next_score = scores[i] / scores[i - k]
        print("Yes" if next_score > 1 else "No")


main()
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
import collections


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()
    As = LI()
    As.sort()
    As.reverse()
    ans = []
    ans.append(As.pop(0))
    N -= 1

    for i in range(len(As)):
        tmp = As.pop(0)
        ans.extend([tmp, tmp])

    print(sum(ans[:N]))


# oj t -c "pypy3 main.py"
# acc s main.py -- --guess-python-interpreter pypy
main()


Fixed submission:
#!/usr/bin/env python3
import sys
import collections


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()
    As = LI()
    As.sort()
    As.reverse()
    As = collections.deque(As)
    ans = []
    tmp = As.popleft()
    ans.append(tmp)

    for i in range(len(As)):
        tmp = As.popleft()
        ans.extend([tmp, tmp])

    print(sum(ans[:N-1]))
    # print(ans)


# oj t -c "pypy3 main.py"
# acc s main.py -- --guess-python-interpreter pypy
main()
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()
    A = LI()

    ans = 1
    index = 0
    while index < N:
        ans *= A[index]
        index += 1

    if ans <= 10**18:
        print(ans)
    else:
        print(-1)


# oj t -c "pypy3 main.py"
# acc s main.py -- --guess-python-interpreter pypy
main()


Fixed submission:
#!/usr/bin/env python3
import sys


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()
    A = LI()

    ans = 1
    index = 0
    A_set = set(A)
    if 0 in A_set:
        print(0)
        return
    while index < N:
        ans *= A[index]
        index += 1
        if ans > 10**18:
            break

    if ans <= 10**18:
        print(ans)
    else:
        print(-1)


# oj t -c "pypy3 main.py"
# acc s main.py -- --guess-python-interpreter pypy
main()
Buggy python submission (verdict: Runtime Error):
from collections import deque


def resolve():
    n, m = map(int, input().split())
    ans = [-1 for i in range(n)]

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

    # stack = []
    # connected_to_one = [*connections[0]]

    # for room in connected_to_one:
    #     ans[room] = 1

    #     connections[0].remove(room)
    #     connections[room].remove(0)

    #     stack.append(room)

    D = deque([0])
    visited = [False]*n
    visited[0] = True

    while D:
        room = D.popleft()

        for i in connections[room]:
            if visited[i]:
                continue
            visited[i] = True
            ans[i] = room + 1
            D.append(i)

    _ans = ans[1:]

    if -1 in _ans:
        print('No')
    else:
        print('Yes')
        for i in _ans:
          
resolve()

Fixed submission:
def resolve():
    a = int(input()[-1])
    hon = [2, 4, 5, 7, 9]
    pon = [0, 1, 6, 8]
    bon = [3]

    for _hon in hon:
        if a == _hon:
            print('hon')
    for _pon in pon:
        if a == _pon:
            print('pon')

    for _bon in bon:
        if a == _bon:
            print('bon')
resolve()
Buggy python submission (verdict: Time Limit Exceeded):
def resolve():
    AHP, AAT, BHP, BAT = list(map(int, input().split()))

    while AHP * BHP > 0:
        AHP -= BAT
        BHP -= AAT

    if BHP <= 0:
        print('Yes')
    else:
        print('No')
resolve()

Fixed submission:

import math


def resolve():
    AHP, AAT, BHP, BAT = list(map(int, input().split()))

    TurnToDieA = math.ceil(AHP / BAT)
    TurnToDieB = math.ceil(BHP / AAT)

    if TurnToDieA < TurnToDieB:
        print('No')
    else:
        print('Yes')

resolve()
Buggy python submission (verdict: Time Limit Exceeded):
def calcGCD3(a,b,c):
    for i in reversed(range(1,a+1)):
        if a % i == 0 and b % i ==0 and c% i ==0:
            return i
    return 0

def calcGCD2(a,b):
    for i in reversed(range(1,a+1)):
        if a % i == 0 and b % i ==0 :
            return i
    return 0
        
ans = 0
n = int(input())
for k in range(1,n+1):
    for b in range(k+1,n+1):
        for c in range(b+1,n+1):
            gcd = calcGCD3(k,b,c)
            ans += gcd

ans *= 6

tmp = 0

for k in range(1, n+1):
    for b in range(k+1, n+1):
        gcd = calcGCD2(k,b)
        tmp += gcd
        
tmp *= 6

tmp2 = sum(range(1,n+1))

print(ans+tmp+tmp2)

Fixed submission:
def dcg(a, b):
    if (b == 0):
        return a
    else:
        return dcg(b, a % b)


ans = 0
n = int(input())
for k in range(1, n+1):
    for b in range(k + 1, n + 1):
        for c in range(b + 1, n + 1):
            gcd1 = dcg(k, b)
            gcd2 = dcg(gcd1, c)
            ans += gcd2

ans *= 6

tmp = 0

for k in range(1, n+1):
    for b in range(k+1, n+1):
        gcd = dcg(k,b)
        tmp += gcd
        
tmp *= 6

tmp2 = sum(range(1,n+1))

print(ans+tmp+tmp2)
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    n, k = MI()
    p = LI()
    max_seq = 0

    for i in range(n - k + 1):
        if sum(p[i : i + k]) > max_seq:
            max_seq = sum(p[i : i + k])

    print((max_seq + k) / 2)


main()


Fixed submission:
#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    n, k = MI()
    p = LI()
    max_seq = sum(p[:k])

    current = sum(p[:k])

    for i in range(k, n):
        current = current - p[i - k] + p[i]
        max_seq = max(max_seq, current)

    print((max_seq + k) / 2)


main()
Buggy python submission (verdict: Time Limit Exceeded):
def check(a, b, c):
    return True if c < a + b else False

def resolve():
    n = int(input())
    targets = list(map(int, input().split()))
    targets.sort()
    ans = 0

    for i in range(len(targets)):
        for j in range(i + 1, len(targets)):
            for k in range(j + 1, len(targets)):
                if check(targets[i], targets[j], targets[k]):
                    ans += 1
                else:
                    continue

    print(ans)
resolve()


Fixed submission:
def check(a, b, c):
    return True if c < a + b else False

import bisect
def resolve():
    n = int(input())
    targets = list(map(int, input().split()))
    targets.sort()
    ans = 0

    for i in range(len(targets)):
        for j in range(i + 1, len(targets)):
            rest = targets[j+1:len(targets)]
            ans += bisect.bisect_left(rest,targets[i]+targets[j])

    print(ans)
resolve()

Buggy python submission (verdict: Time Limit Exceeded):
def check(a, b, c):
    return True if a < b + c and b < a + c and c < a + b else False

def resolve():
    n = int(input())
    targets = list(map(int, input().split()))
    ans = 0

    for i in range(len(targets)):
        for j in range(i + 1,len(targets)):
            for k in range(j + 1,len(targets)):
                if check(targets[i],targets[j],targets[k]):
                    ans += 1



    print(ans)
resolve()


Fixed submission:
def check(a, b, c):
    return True if c < a + b else False

import bisect
def resolve():
    n = int(input())
    targets = list(map(int, input().split()))
    targets.sort()
    ans = 0

    for i in range(len(targets)):
        for j in range(i + 1, len(targets)):
            rest = targets[j+1:len(targets)]
            ans += bisect.bisect_left(rest,targets[i]+targets[j])

    print(ans)
resolve()

Buggy python submission (verdict: Time Limit Exceeded):
def check(a, b, c):
    return True if a < b + c and b < a + c and c < a + b else False

def resolve():
    n = int(input())
    targets = list(map(int, input().split()))
    ans = 0

    for i in range(len(targets)):
        for j in range(i + 1,len(targets)):
            for k in range(j + 1,len(targets)):
                if check(targets[i],targets[j],targets[k]):
                    ans += 1



    print(ans)
resolve()


Fixed submission:
def check(a, b, c):
    return True if c < a + b else False

import bisect
def resolve():
    n = int(input())
    targets = list(map(int, input().split()))
    targets.sort()
    ans = 0

    for i in range(len(targets)):
        for j in range(i + 1, len(targets)):
            rest = targets[j+1:len(targets)]
            ans += bisect.bisect_left(rest,targets[i]+targets[j])

    print(ans)
resolve()
Buggy python submission (verdict: Time Limit Exceeded):

inf = 10**10


def resolve():
    n, m, gas = map(int, input().split())

    costs = [[inf for i in range(n)] for i in range(n)]

    for i in range(len(costs)):
        costs[i][i] = 0
    for i in range(m):
        v1, v2, cost = map(int, input().split())
        costs[v1 - 1][v2 - 1] = cost
        costs[v2 - 1][v1 - 1] = cost

    for k in range(n):
        for i in range(n):
            for j in range(n):
                costs[i][j] = min(costs[i][j], costs[i][k]+costs[k][j])

    cost_with_gas = [[inf for i in range(n)] for i in range(n)]

    for i in range(len(cost_with_gas)):
        cost_with_gas[i][i] = 0
    for i in range(len(cost_with_gas)):
        for j in range(i+1, len(cost_with_gas)):
            if gas - costs[i][j] >= 0:
                cost_with_gas[i][j] = 1
                cost_with_gas[j][i] = 1

    for k in range(n):
        for i in range(n):
            for j in range(n):
                cost_with_gas[i][j] = min(cost_with_gas[i][j], cost_with_gas[i][k]+cost_with_gas[k][j])

    q = int(input())

    for i in range(q):
        from_city, destination = map(int, input().split())
        ans = cost_with_gas[from_city-1][destination-1] -1 if cost_with_gas[from_city-1][destination-1] != inf else -1
        print(ans)
        
resolve()


Fixed submission:
inf = 10**10


def resolve():
    n, m, gas = map(int, input().split())

    costs = [[inf for i in range(n)] for i in range(n)]

    for i in range(len(costs)):
        costs[i][i] = 0
    for i in range(m):
        v1, v2, cost = map(int, input().split())
        costs[v1 - 1][v2 - 1] = cost
        costs[v2 - 1][v1 - 1] = cost

    for k in range(n):
        for i in range(n):
            for j in range(n):
                costs[i][j] = min(costs[i][j], costs[i][k]+costs[k][j])

    cost_with_gas = [[inf for i in range(n)] for i in range(n)]

    for i in range(len(cost_with_gas)):
        cost_with_gas[i][i] = 0
    for i in range(len(cost_with_gas)):
        for j in range(i+1, len(cost_with_gas)):
            if gas - costs[i][j] >= 0:
                cost_with_gas[i][j] = 1
                cost_with_gas[j][i] = 1

    for k in range(n):
        for i in range(n):
            for j in range(n):
                cost_with_gas[i][j] = min(cost_with_gas[i][j], cost_with_gas[i][k]+cost_with_gas[k][j])

    q = int(input())

    for i in range(q):
        from_city, destination = map(int, input().split())
        ans = cost_with_gas[from_city-1][destination-1] -1 if cost_with_gas[from_city-1][destination-1] != inf else -1
        print(ans)

resolve()