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

import sys
# sys.stdin = open('input.txt')

from math import gcd


n = int(input())
s = input()
i_indices = []
j_indices = []
k_indices = []

for i in range(n):
    if s[i] == 'R':
        i_indices.append(i+1)
    elif s[i] == 'G':
        j_indices.append(i+1)
    else:
        k_indices.append(i+1)

# print(i_indices, len(i_indices))
# print(j_indices, len(j_indices))
# print(k_indices, len(k_indices))

ans = 0

for i in i_indices:
    for j in j_indices:
        for k in k_indices:
            a, b, c = i, j, k
            if b - a != c - b and a < b < c:
                ans += 1
            a, b, c = i, k, j
            if b - a != c - b and a < b < c:
                ans += 1
            a, b, c = j, i, k
            if b - a != c - b and a < b < c:
                ans += 1
            a, b, c = j, k, i
            if b - a != c - b and a < b < c:
                ans += 1
            a, b, c = k, i, j
            if b - a != c - b and a < b < c:
                ans += 1
            a, b, c = k, j, i
            if b - a != c - b and a < b < c:
                ans += 1

print(ans)

### FIXED CODE ###

import time
start = time.time()
import sys
# sys.stdin = open('input.txt')

n = int(input())
s = input()
# r = []
# g = []
# b = []
#
# for i in range(n):
#     if s[i] == 'R':
#         r.append(i)
#     elif s[i] == 'G':
#         g.append(i)
#     else:
#         b.append(i)


ans = s.count('R') * s.count('G') * s.count('B')
# print(ans)

for j in range(n):
    for i in range(j):
        k = 2 * j - i
        if k < n:
            if s[i] != s[j] and s[i] != s[k] and s[j] != s[k]:
                ans -= 1

print(ans)
# end = time.time()
# print(end - start)
### BUGGY CODE ###

n, k = map(int,input().split())
pointer = 0
while (k**pointer <= n):
  if k**pointer < n:
    pointer += 1
    
print(pointer)

### FIXED CODE ###

n, k = map(int,input().split())
pointer = 0
while (k**pointer <= n):
    pointer += 1
    
print(pointer)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
L = [int(i) for i in input().split()]
total = 0

for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            if L[i] < L[j]+L[k] and L[j] < L[i]+L[k] and L[k] < L[i]+L[j]:
                total +=1

print(total)


### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
L = [int(i) for i in input().split()]
total = 0

L = sorted(L)

for i in range(N-2):
    k = i + 2
    for j in range(i+1, N):
        while k < N and L[i] + L[j] > L[k]:
            k+=1
        if k > j:
            total += k-j-1

print(total)
### BUGGY CODE ###

import bisect

n = int(input())
vx, vy = [], []
for _ in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    if x1 == x2:
        if y1 > y2:
            y1, y2 = y2, y1
        vx.append((x1, y1, y2))
    else:
        if x1 > x2:
            x1, x2 = x2, x1
        vy.append((y1, x1, x2))
vy.sort()

ans = 0
cache = {}

for x, y1, y2 in vx:
    y2 += 1
    if y1 not in cache:
        it1 = cache[y1] = bisect.bisect(vy, (y1,))
    else:
        it1 = cache[y1]
    if y2 not in cache:
        it2 = cache[y2] = bisect.bisect(vy, (y2,))
    else:
        it2 = cache[y2]
    ans += sum(x1 <= x <= x2 for y, x1, x2 in vy[it1:it2])

print(ans)

### FIXED CODE ###

import bisect


class BIT:
    def __init__(self, n):
        self.tree = [0] * (n + 1)
        self.n = n

    def add(self, i, v):
        while i <= self.n:
            self.tree[i] += v
            i += i & -i

    def _sum(self, i):
        ret = 0
        while i:
            ret += self.tree[i]
            i -= i & -i
        return ret

    def sum(self, l, h):
        return self._sum(h) - self._sum(l - 1)


n = int(input())
vx = []
xs = set()
for _ in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    if x1 == x2:
        if y1 > y2:
            y1, y2 = y2, y1
        vx.append((y1, float('-inf'), x1))
        vx.append((y2, float('inf'), x1))
        xs.add(x1)
    else:
        if x1 > x2:
            x1, x2 = x2, x1
        vx.append((y1, x1, x2))
vx.sort()

bit = BIT(len(xs))
xs = [float('-inf')] + sorted(xs)
ix = {v: i for i, v in enumerate(xs)}
ans = 0

for y, j, x2 in vx:
    if j == float('-inf'):
        bit.add(ix[x2], 1)
    elif j == float('inf'):
        bit.add(ix[x2], -1)
    else:
        i1 = bisect.bisect_left(xs, j)
        i2 = bisect.bisect(xs, x2) - 1
        ans += bit.sum(i1, i2)

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

#!/usr/bin/env python3

import functools

try:
    from math import gcd
except ImportError:
    from fractions import gcd


def gcds(xs):
    return functools.reduce(gcd, xs)


def lcm(a, b):
    return a // gcd(a, b) * b


def lcms(xs):
    return functools.reduce(lcm, xs)


def prods(xs):
    return functools.reduce(lambda a, b: a * b, xs)


def is_pairwise_coprime(xs):
    return lcms(xs) == prods(xs)


def is_setwise_coprime(xs):
    return gcds(xs) == 1


def main():
    n = int(input())
    bs = [int(b) for b in input().split()]
    if is_pairwise_coprime(bs):
        print("pairwise coprime")
    elif is_setwise_coprime(bs):
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3


import collections
import functools
from math import gcd


L = 10 ** 6 + 1


def sieve_of_eratosthenes(end):
    """Enumerates prime numbers below the given integer `end`.

    Returns (as a tuple):

    - `is_prime`: a list of bool values.
      If an integer `i` is a prime number, then `is_prime[i]` is True.
      Otherwise `is_prime[i]` is False.
    - `primes`: a list of prime numbers below `end`.
    """

    if end <= 1:
        raise ValueError("The integer `end` must be greater than one")
    is_prime = [True for _ in range(end)]
    is_prime[0] = False
    is_prime[1] = False
    primes = []
    for i in range(2, end):
        if is_prime[i]:
            primes.append(i)
            for j in range(2 * i, end, i):
                is_prime[j] = False
    return primes


PRIMES = sieve_of_eratosthenes(L)


def factorize(n):
    factors = []
    if n < 2:
        return factors
    for p in PRIMES:
        if p * p > n:
            break
        while n % p == 0:
            factors.append(p)
            n //= p
    if n > 1:
        factors.append(n)
    return factors


def is_pairwise_coprime(bs):
    lcm_fs = set()
    for b in bs:
        ps = set(factorize(b))
        for p in ps:
            if p in lcm_fs:
                return False
            else:
                lcm_fs.add(p)
    return True


def is_setwise_coprime(bs):
    return functools.reduce(gcd, bs) == 1


def main():
    n = int(input())
    bs = [int(b) for b in input().split()]
    if is_pairwise_coprime(bs):
        print("pairwise coprime")
    elif is_setwise_coprime(bs):
        print("setwise coprime")
    else:
        print("not coprime")


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

# from pprint import pprint

N, M = map(int, input().split())
A = []
C = []
for _ in range(M):
    a, b = map(int, input().split())
    A.append(a)
    c = map(lambda x: int(x)-1, input().split())
    state = 0
    for ci in c:
        state |= 1 << ci
    C.append(state)

INF = 10**18
dp = [[INF]*2**N for _ in range(M)]
dp[0][0] = 0

for i in range(M-1):
    for state in range(1 << N):
        used = state | C[i]
        cur = dp[i][state]
        if dp[i+1][used] > cur + A[i]:
            dp[i+1][used] = dp[i][state] + A[i]

        if dp[i+1][state] > cur:
            dp[i+1][state] = cur

ans = dp[-1][-1]
print(ans if ans != INF else -1)


### FIXED CODE ###

import sys
import itertools

N,M = map(int, input().split())
AB = []
C = []
for _ in range(M):
    AB.append(tuple(map(int, input().split())))
    C.append(sum(1<<(int(x)-1) for x in map(int, input().split())))

INF = 10**18
dp = [INF]*(1<<N)
dp[0] = 0

for n,((a,b),c) in itertools.product(range(1<<N), zip(AB,C)):
    m = n|c
    x = dp[n] + a
    if dp[m] > x:
        dp[m] = x

ans = dp[-1]
if ans == INF:
    ans = -1
print(ans)
### BUGGY CODE ###


class Point():
  def __init__(self, x, y):
    self.x = x
    self.y = y
  
  def __str__(self):
    # return f"Point(x={self.x}, y={self.y})"
    return "Point(x=" + str(self.x) + ", y=" + str(self.y) + ")"

  def __repr__(self):
    return self.__str__()

def parse():
  H, W = map(int, input().split(" "))
  grid = []
  for h in range(H):
    grid.append(list(input()))
  return H, W, grid

def print_grid(grid):
  H = len(grid)
  print("grid:")
  for y in range(H):
    print(grid[y])

def is_all_black(grid):
  H = len(grid)
  W = len(grid[0])
  for y in range(H):
    for x in range(W):
      if grid[y][x] == ".": return False
  return True

def main():
  H, W, grid = parse()
  # print(H, W, grid)

  vecs = [Point(0, -1), Point(0, 1), Point(-1, 0), Point(1, 0)]
  
  # 初期の黒色の場所を追加
  black_points = []
  for y in range(H):
    for x in range(W):
      if grid[y][x] == "#":
        black_points.append(Point(x, y))
  # print(black_points)

  ans = 0
  while len(black_points) > 0:
  # while not is_all_black(grid):
    next_black_points = []
    for black_point in black_points:
      # print("black_point:", black_point)
      for vec in vecs:
        target_point = Point(black_point.x + vec.x, black_point.y + vec.y)
        if target_point.x < 0: continue
        if target_point.y < 0: continue
        if target_point.x >= W: continue
        if target_point.y >= H: continue
        if grid[target_point.y][target_point.x] == "#": continue
        grid[target_point.y][target_point.x] = "#"
        next_black_points.append(target_point)
    black_points = next_black_points
    ans += 1

    # print("next_black_points:", next_black_points)
    # print_grid(grid)
    # input()
  
  print(ans - 1)

if __name__ == "__main__":
  main()

### FIXED CODE ###


import numpy as np

def parse():
  H, W = map(int, input().split(" "))
  grid = [list(input()) for y in range(H)]
  return H, W, grid

def print_grid(grid):
  H = len(grid)
  print("grid:")
  for line in grid:
    for c in line:
      print(c, end="")
    print("")

def main():
  H, W, grid = parse()
  # print(H, W)
  # print_grid(grid)

  # visited = [[W * H if grid[y][x] == "." else 0 for x in range(W)] for y in range(H)]
  visited = np.zeros((H, W), int)
  for y in range(H):
    # visited.append([])
    for x in range(W):
      if grid[y][x] == ".":
        visited[y][x] = H * W

  for y in range(1, H):  # ↓
    # 要素ごとの処理
    # print(visited)
    visited[y][:] = np.minimum(visited[y][:], visited[y - 1][:] + 1)
    # print(visited)
    # input()
    # print(visited[y])
    # exit(0)

  for y in range(H - 2, -1, -1):
    visited[y, :] = np.minimum(visited[y, :], visited[y + 1][:] + 1)

  for x in range(1, W):
    visited[:, x] = np.minimum(visited[:, x], visited[:, x - 1] + 1)

  for x in range(W - 2, -1, -1):
    visited[:, x] = np.minimum(visited[:, x], visited[:, x + 1] + 1)

  # print(visited)
  # exit(0)

  # max_len = 0
  # for y in range(H):
  #   max_val = max(visited[y])
  #   max_len = max_len if max_len > max_val else max_val
  # print(max_len)
  print(np.max(visited))

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

n = int(input())

dlist = []

for i in range(n):
    arr = input().split()
    cmd = ''
    key = 0
    cmd = arr[0]
    if len(arr) > 1:
        key = int(arr[1])
    if cmd == 'insert':
        dlist.insert(0, key)
    elif cmd == 'delete':
        if dlist.count(key) > 0:
            idx = dlist.index(key)
            if idx != -1:
                dlist.pop(idx)
    elif cmd == 'deleteFirst':
        dlist.pop(0)
    elif cmd == 'deleteLast':
        dlist.pop(-1)

print(' '.join(map(str, dlist)))



### FIXED CODE ###

from collections import deque

n = int(input())

dlist = deque()

for i in range(n):
    arr = input().split()
    cmd = ''
    key = 0
    cmd = arr[0]
    if len(arr) > 1:
        key = arr[1]
    if cmd == 'insert':
        dlist.appendleft(key)
    elif cmd == 'delete':
        try:
            dlist.remove(key)
        except:
            continue
    elif cmd == 'deleteFirst':
        dlist.popleft()
    elif cmd == 'deleteLast':
        dlist.pop()

print(' '.join(dlist))
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
ex=[0]*1000001
for a in A:ex[a]+=1
cnt=0
for a in A:
    ex[a]-=1
    i=1
    while i*i<=a:
        if a%i==0 and(ex[i]>0 or ex[a//i]>0):
            break
        i+=1
    else:
        cnt+=1
    ex[a]+=1
print(cnt)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
ex=[0]*1000001
for a in A:ex[a]+=1
cnt=0
for i in range(1,1000001):
    if ex[i]>0:
        for j in range(i+i,1000001,i):ex[j]=0
        if ex[i]==1:
            cnt+=1
print(cnt)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    n,k=map(int,input().split())
    X=[0]*n
    Y=[0]*n
    for i in range(n):
        X[i],Y[i]=map(int,input().split())
    ans=INF
    for a in range(n):
        for b in range(n):
            for c in range(a+1,n):
                for d in range(b+1):
                    x0,x1=sorted([X[a],X[c]])
                    y0,y1=sorted([Y[b],Y[d]])
                    if k<=sum((x0<=X[i]<=x1 and y0<=Y[i]<=y1) for i in range(n)):
                        ans=min(ans,(x1-x0)*(y1-y0))
    print(ans)
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    n,k=map(int,input().split())
    X=[0]*n
    Y=[0]*n
    for i in range(n):
        X[i],Y[i]=map(int,input().split())
    ans=INF
    for a in range(n):
        for b in range(n):
            for c in range(a+1,n):
                for d in range(b+1):
                    x0,x1=sorted([X[a],X[c]])
                    y0,y1=sorted([Y[b],Y[d]])
                    count=0
                    for i in range(n):
                        if x0<=X[i]<=x1 and y0<=Y[i]<=y1:
                            count+=1
                    if count>=k:
                        ans=min(ans,(x1-x0)*(y1-y0))
    print(ans)
resolve()
### BUGGY CODE ###

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

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

#print(h)

o = [0]* n

for a in range(1,n):
    o[a] = min(o[b]+abs(h[a]-h[b]) for b in range(max(0,a-k),a))

print(o[-1])





### FIXED CODE ###

def main():
	N, K = map(int, input().split())
	h = list(map(int, input().split()))
 
	dp=[0]*N
 
	for i in range(1,N):
		dp[i] = min(
			dp[g] + abs(h[i] - h[g]) for g in range(max(i-K,0), i)
		)
	print(dp[N-1])
main()
### BUGGY CODE ###

n = int(input())
power = 1

for i in range(1, n + 1):
  power = i * power

amari = (10 ** 9) + 7
print(int(power % amari))

### FIXED CODE ###

n = int(input())
power = 1

for i in range(1, n + 1):
  power = (i * power) % ((10 ** 9) + 7)

print(power)
### BUGGY CODE ###

from collections import Counter

N = int(input())
cnts = []
for i in range(N):
    cnts.append(Counter(list(input())))

res = 0
for i in range(N):
    for j in range(i + 1, N):
        chk = 1
        for k in range(26):
            kc = chr(ord('a') + k)
            if cnts[i][kc] != cnts[j][kc]:
                chk = 0
                break
        res += chk
print(res)

### FIXED CODE ###

def f(x):
    return 10 ** (ord(x) - ord('a') + 1)


import math


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


from collections import Counter

N = int(input())
counter = Counter()
for i in range(N):
    counter[sum([f(i) for i in input()])] += 1
res = 0
for v in counter.values():
    if v > 1:
        res += combinations_count(v, 2)
print(res)
### BUGGY CODE ###

#!/usr/bin/env python3

A, B, N = map(int, input().split())
num = 0
ans = 0

for x in range(1, N+1):
    num = (A*x)//B - A*(x//B)
    ans = max(ans, num)
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3

A, B, N = map(int, input().split())
num = 0
ans = 0

if N >= B:
    print((A*(B-1))//B - A*((B-1)//B))
else:
    print((A*N)//B - A*(N//B))
### BUGGY CODE ###


import sys

N, Y = map(int, input().split())
max1000 = int(Y/1000)
for z in range(max1000, -1, -5):
    max5000 = int((max1000-z) / 5)
    for y in range(0, max5000+1):
        x = N - y - z
        if x*10000 + y*5000 + z*1000 == Y:
            print(str(x) + ' ' + str(y) + ' ' + str(z))
            sys.exit()
print("-1 -1 -1")

### FIXED CODE ###


import sys

N, Y = map(int, input().split())
max1000 = int(Y/1000)
c1000 = [i for i in range(max1000, -1, -5) if i <= N]
for z in c1000:
    max5000 = int((max1000-z) / 5)
    for y in range(0, max5000+1):
        x = N - y - z
        if x*10000 + y*5000 + z*1000 == Y:
            print(str(x) + ' ' + str(y) + ' ' + str(z))
            sys.exit()
print("-1 -1 -1")
### BUGGY CODE ###

from collections import deque
def main():
  s = deque(list(input()))
  q = int(input())
  sr = s.reverse
  sa = s.append
  sal = s.appendleft

  cnt = 0
  for _ in range(q):
    t = input()
    if t[0] == "1":
      cnt += 1
    else:
      if cnt%2 == 1:
        sr()
        cnt = 0
      _,f,c = t.split(" ")
      if f == "1":
        sal(c)
      else:
        sa(c)
  if cnt%2 == 1:
    sr()
  print("".join(list(s)))

if __name__=="__main__":
  main()

### FIXED CODE ###

from collections import deque
def main():
  s = deque(list(input()))
  q = int(input())
  sr = s.reverse
  sa = s.append
  sal = s.appendleft

  cnt = 0
  for _ in range(q):
    t = input()
    if t[0] == "1":
      cnt += 1
    else:
      _,f,c = t.split(" ")
      if f == "1":
        if cnt%2==1:
          sa(c)
        else:
          sal(c)
      else:
        if cnt%2==1:
          sal(c)
        else:
          sa(c)
  if cnt%2 == 1:
    sr()
  print("".join(list(s)))

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

n, k = map(int, input().split())
ans = n
done = [n]

if k == 1:
    print(0)
else:
    while 1:
        n = abs(n-k)
        ans = min(ans, n)

        if n in done or n == 0:
            break
        else:
            done.append(n)
    print(ans)

### FIXED CODE ###

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

if n == 0 or k == 1:
    print(0)
else:
    if n > k:
        n %= k
    print(min(n, k-n))
### BUGGY CODE ###

N = int(input())
D = input().split()
D = [int(d) for d in D]
if(D[0] != 0):
    print(0)
else:
    D = sorted(D[1:])
    if(D[-1]==1):
        print(1)
    else:
        n = 0
        k = 0
        mul = 1
        k_count_before = 1
        while(n<len(D)):
            k += 1
            k_count = 0
            
            while(n<len(D) and D[n]==k):
                k_count += 1
                n += 1

            if(k_count==0):
                mul = 0
            else:

                mul *= k_count_before**k_count
                k_count_before = k_count

        print(mul%998244353)

### FIXED CODE ###

N = int(input())
D = input().split()
D = [int(d) for d in D]

hantei = 1
if(D[0] != 0):
    print(0)
else:
    D = sorted(D[1:])
    if(D[-1]==1):
        print(1)
    else:
        n = 0
        k = 0
        mul = 1
        k_count_before = 1
        while(n<len(D)):
            k += 1
            k_count = 0
            
            while(n<len(D) and D[n]==k):
                k_count += 1
                n += 1

            if(k_count==0):
                mul = 0
                hantei = 0
                break
            else:

                mul *= k_count_before**k_count
                k_count_before = k_count

        print(mul%998244353)
### BUGGY CODE ###

def main():
    N = int(input().strip())
    a = list(map(int, input().strip().split()))
    min_v = float("inf")
    for i in range(1, N):
        x = sum(a[:i])
        y = sum(a[i:])
        min_v = min(min_v, abs(x - y))
    print(min_v)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))

    solve(N,A)

def solve(N,A):
    ans = float("inf")

    # ans = TLE(N,A,ans)
    ans = AC(N,A,ans)

    print(ans)

def TLE(N,A, ans):
    for i in range(1, N):
        snk = sum(A[:i])
        ari = sum(A[i:])

        ans = min(ans, abs(snk - ari))

    return ans

def AC(N,A,ans):
    cum_A = [None] * N
    cum_A[0] = A[0]
    for i in range(1, N):
        cum_A[i] = cum_A[i-1] + A[i]

    for i in range(N-1):
        snk = cum_A[i]
        ari = cum_A[-1] - snk

        ans = min(ans, abs(snk - ari))

    return ans

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

a,b,k=map(int,input().split())
for i in range(0,k):
  if a>=1:
    a=a-1
  elif b>=1:
    b=b-1
print("{} {}".format(a,b))

### FIXED CODE ###

a,b,k=map(int,input().split())
if a>=k:
  a=a-k
else:
  b=b-(k-a)
  a=0
b=max(0,b)
print("{} {}".format(a,b))
### BUGGY CODE ###

import numpy as np

def warshall_floyd(V, d):

    return d

INF = 10 ** 9
n, m, l = map(int, input().split())
d = [[INF for j in range(n + 1)] for i in range(n + 1)]
d2 = [[INF for j in range(n + 1)] for i in range(n + 1)]
for _ in range(m):
    i, j, c = map(int, input().split())
    d[i][j] = c
    d[j][i] = c
    if c <= l:
        d2[i][j] = 1
        d2[j][i] = 1

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

for k in range(1, n + 1):
    for i in range(1, n):
        for j in range(i, n + 1):
            dk = d[i][k] + d[k][j]
            if d[i][j] > dk:
                d[i][j] = dk
                d[j][i] = dk
                if dk <= l:
                    d2[i][j] = 1
                    d2[j][i] = 1

for k in range(1, n + 1):
    for i in range(1, n):
        for j in range(i, n + 1):
            dk = d2[i][k] + d2[k][j]
            if d2[i][j] > dk:
                d2[i][j] = dk
                d2[j][i] = dk

for i in range(q):
    s, t = Q[i]
    di = d2[s][t]
    if di >= INF:
        print(-1)
    else:
        print(di - 1)


### FIXED CODE ###

INF = 10 ** 9
n, m, l = map(int, input().split())
d = [[INF for j in range(n + 1)] for i in range(n + 1)]
d2 = [[INF for j in range(n + 1)] for i in range(n + 1)]
for _ in range(m):
    i, j, c = map(int, input().split())
    d[i][j] = c
    d[j][i] = c
    if c <= l:
        d2[i][j] = 1
        d2[j][i] = 1

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

for k in range(1, n + 1):
    for i in range(1, n):
        for j in range(i, n + 1):
            dk = d[i][k] + d[k][j]
            if d[i][j] > dk:
                d[i][j] = dk
                d[j][i] = dk
                if dk <= l:
                    d2[i][j] = 1
                    d2[j][i] = 1

for k in range(1, n + 1):
    for i in range(1, n):
        for j in range(i, n + 1):
            dk = d2[i][k] + d2[k][j]
            if d2[i][j] > dk:
                d2[i][j] = dk
                d2[j][i] = dk

for i in range(q):
    s, t = Q[i]
    di = d2[s][t]
    if di >= INF:
        print(-1)
    else:
        print(di - 1)