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

import sys
from queue import Queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000000)

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

A = [-1]*M
B = [-1]*M
C = [-1]*M
nodes_edges = [[] for _ in range(N)]
rev_nodes_edges = [[] for _ in range(N)]
coin = [-float('inf')]*N
coin[0] = 0
availables = set()

for edge in range(M):
    a, b, c = map(int, input().split())
    A[edge] = a-1
    B[edge] = b-1
    C[edge] = c-P
    nodes_edges[a-1].append(edge)
    rev_nodes_edges[b-1].append(edge)

def cut_graph(node):
    edges = rev_nodes_edges[node]
    availables.add(node)
    for edge in edges:
        prev = A[edge]
        if prev in availables:
            continue
        cut_graph(prev)

cut_graph(N-1)
q = Queue()
q.put(0)
count = 0
limit = len(availables) + N * M
while not q.empty():
    if count == limit:
        print(-1)
        break
    node = q.get()
    edges = nodes_edges[node]
    for edge in edges:
        nxt = B[edge]
        if nxt not in availables:
            continue
        new_coin = C[edge]+coin[node]
        if new_coin > coin[nxt]:
            coin[nxt] = new_coin
            q.put(nxt)
    count += 1
else:
    ans = coin[N-1]
    ans = 0 if ans < 0 else ans
    print(ans)

### FIXED CODE ###

import sys
import time
from queue import Queue
limit_time = time.time() + 1.70
input = sys.stdin.readline
sys.setrecursionlimit(1000000000)

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

A = [-1]*M
B = [-1]*M
C = [-1]*M
nodes_edges = [[] for _ in range(N)]
rev_nodes_edges = [[] for _ in range(N)]
coin = [-float('inf')]*N
coin[0] = 0
availables = set()

for edge in range(M):
    a, b, c = map(int, input().split())
    A[edge] = a-1
    B[edge] = b-1
    C[edge] = c-P
    nodes_edges[a-1].append(edge)
    rev_nodes_edges[b-1].append(edge)

def cut_graph(node):
    edges = rev_nodes_edges[node]
    availables.add(node)
    for edge in edges:
        prev = A[edge]
        if prev in availables:
            continue
        cut_graph(prev)

cut_graph(N-1)
q = Queue()
q.put(0)
count = 0
limit = M*(1+len(availables))
while not q.empty():
    if time.time() >= limit_time:
        print(-1)
        break
    node = q.get()
    edges = nodes_edges[node]
    for edge in edges:
        nxt = B[edge]
        if nxt not in availables:
            continue
        new_coin = C[edge]+coin[node]
        if new_coin > coin[nxt]:
            coin[nxt] = new_coin
            q.put(nxt)
    count += 1
else:
    ans = coin[N-1]
    ans = 0 if ans < 0 else ans
    print(ans)
### BUGGY CODE ###

a,b=map(int,input().split())
l=list(map(int,input().split()))
for i in range(min(b,1000)):
  now=[0]*a
  for j in range(a):
    x=l[j]
    for k in range(max(0,j-x),min(a,j+x+1)):
      now[k]+=1
  l=now
for i in range(a):
  now[i]=min(now[i],a)
print(*now)


### FIXED CODE ###

a,b=map(int,input().split())
l=list(map(int,input().split()))
import itertools
b=min(b,50)
def ku(l):
    y=[0]*a
    for j,x in enumerate(l):
      y[max(0,j-x)]+=1
      r=min(j+x,a-1)
      if r<a-1:
        y[r+1]-=1
    return itertools.accumulate(y)

  
for _ in range(b):
  l=ku(l)
print(*l)
### BUGGY CODE ###

import numpy as np
N, K = map(int, input().split())
h = [int(x) for x in input().split()]

cost = np.full(N, float("inf"))
cost[0] = 0

for i in range(1, N):
    hi_cost = h[i]
    cost_list = [ abs(hi_cost - h[j]) + cost[j] for j in range(max(0, i-K), i)]
    cost[i] = min(cost_list)
    
print(int(cost[N-1]))

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
hights = np.array(list(map(int,input().split())))
steps=np.array([0]*N)
steps[0]=0

for i in range(1, N):
    gaps = hights[max(0, i-K):i] - hights[i]
    gaps = np.abs(gaps)
    gaps += steps[max(0, i-K):i]
    steps[i] = np.min(gaps)
    
print(int(steps[N-1]))
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline

    n, m = map(int, input().split())
    query = []
    result =  [[] for i in range(n)]
    for _ in range(m):
        p, y = map(int, input().split())
        query.append((p, y))
        result[p-1].append(y)

    result = [sorted(i) for i in result]
 
    for city in query:
        rank = result[city[0]-1].index(city[1])+1
        resultStr = "{}{}".format(str(city[0]).zfill(6), str(rank).zfill(6))
        print(resultStr)

main()

### FIXED CODE ###

def main():
    from sys import stdin
    from bisect import bisect_left

    readline = stdin.readline
    n, m = map(int, readline().split())
    data = [list(map(int, readline().split())) for _ in range(m)]
    t = [[] for _ in range(n)]

    for p, y in data:
        t[p - 1].append(y)

    for i in range(n):
        t[i].sort()

    for p, y in data:
        nth = bisect_left(t[p - 1], y) + 1
        print("%06d%06d" % (p, nth))

main()
### BUGGY CODE ###


n,m = map(int,input().split())
h = list(map(int,input().split()))
x = []
ab = []
c = 0
for i in range(m):
    ab.extend(list(map(int,input().split())))
for j in range(n):
    p = ab.count(j+1)
    if p == 0:
        x[len(x):len(x)] = [0]
    else:
        x[len(x):len(x)] = [p]
for k in range(m):
    if h[(ab[2*k+1])-1] - h[(ab[2*k])-1] > 0:
        x[(ab[2*k+1])-1] -= 1
    elif h[(ab[2*k])-1] - h[(ab[2*k+1])-1] > 0:
        x[(ab[2*k])-1] -= 1

for l in range(len(x)):
    if x[l] == 0:
        c += 1

print(c)

### FIXED CODE ###

n,m = map(int,input().split())
h = list(map(int,input().split()))
target = [0 for _ in range(n)]
win = [0 for _ in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    target[a-1] += 1
    target[b-1] += 1
    if h[a-1] > h[b-1]:
        win[a-1] += 1
    elif h[b-1] > h[a-1]:
        win[b-1] += 1

count = 0
for j in range(n):
    if target[j] == win[j]:
        count += 1

print(count)
### BUGGY CODE ###

h = int(input())
list = []
list.append(h)
count = 0
while list.count(1) != len(list) :
    max_index = list.index(max(list))
    list[max_index] //= 2
    list.append(list[max_index])
    count += 1
print(count+len(list))


### FIXED CODE ###

h = int(input())
layer = 0
branch_set = 0
while True :
    if h > 1 :
        h //= 2
        layer += 1
        continue
    else :
        break

for i in range(0, layer) :
    branch_set += 2 ** i

print(branch_set + 2**layer)
### BUGGY CODE ###

a, b, n = map(int, input().split())

def f(x):
    return ((a * x) // b) - (a * (x // b))

if n < b - 1:
    max = f(n)
else:
    x = b - 1
    max = f(x)
    while x <= n:
        if max < f(x):
            max = f(x)
        x += b

print(max)

### FIXED CODE ###

a, b, n = map(int, input().split())

def f(x):
    return ((a * x) // b) - (a * (x // b))

if n < b - 1:
    max = f(n)
elif b == 1:
    max = 0
else:
    x = b - 1
    max = f(x)
    while x <= n:
        if max < f(x):
            max = f(x)
        x += b

print(max)
### BUGGY CODE ###

#!/usr/bin/env python3
import fractions
import sys
import functools
sys.setrecursionlimit(10 ** 7)


def solve(N: int, A: "List[int]"):
    ans = 0
    for i in range(N):
        ans = max(ans, functools.reduce(fractions.gcd, A[0:i] + A[i + 1:]))
    print(ans)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools
# (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
from fractions import gcd
import sys
sys.setrecursionlimit(10 ** 7)


def solve(N: int, A: "List[int]"):
    L, R = [0], [0]
    for i in range(N - 1):
        L.append(gcd(L[i], A[i]))
        R.append(gcd(R[i], A[-i - 1]))
    ans = 0
    for i in range(N):
        ans = max(ans, gcd(L[i], R[N - i - 1]))
    print(ans)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools
# (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


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

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
def main():
    N = int(input())
    A = input().split()
    
    ans = set()
    ans_str = ""
    for i in range(N, 0, -1):
        cons = 0
        for j in range(i, N+1, i):
            if j in ans:
                cons += 1
        if A[i-1] == "1" and cons % 2 == 0:
            ans.add(i)
            ans_str = ans_str + str(i) + " "
            continue
        if A[i-1] == "0" and cons % 2 == 1:
            ans.add(i)
            ans_str = ans_str + str(i) + " "
            continue
            
    print(len(ans))
    print(ans_str)
            	
if __name__ == "__main__":
	main()


### FIXED CODE ###

import sys
 
def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7
 
N=INT()
A=LIST()
 
# その位置にボールを入れるかを保持するA2
A2=[0]*N
B=[]
# 後ろから決めていく
for i in range(N-1, -1, -1):
    cur=i+1
    cnt=0
    # curの倍数を全部見に行く
    for j in range(cur*2, N+1, cur):
        cnt^=A2[j-1]
    # ボールを入れるべきかどうか
    if A[i]!=cnt:
        B.append(cur)
        A2[i]=1
 
print(len(B))
print(*B)
### BUGGY CODE ###

n = int(input())

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

ans = 0

for a_i in a:
    if ans == 0:
        ans = a_i
    else:
        ans *= a_i

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

### FIXED CODE ###

n = int(input())

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

ans = 1

flag_0 = False

if 0 in a:
    print(0)
else:
    for a_i in a:
        ans *= a_i
        if ans > 10**18:
            ans = -1
            break
    print(ans)
### BUGGY CODE ###

#4
x,y,z,k=map(int,input().split())
listx = [int(i) for i in input().split()]
listy = [int(i) for i in input().split()]
listz = [int(i) for i in input().split()]

import numpy as np
listxy = np.zeros([x*y,],dtype=np.int)
c = 0
for i in range(0,x):
    for j in range(0,y):
        listxy[c] = listx[i]+listy[j]
        c+=1

listxy = sorted(listxy,reverse=True)
#print(listxy)
if x*y>k:
    listxy=listxy[:k]
    listxyz =np.zeros([k*z,],dtype=np.int)
    c = 0
    for i in range(0,k):
        for j in range(0,z):
            listxyz[c] = listxy[i]+listz[j]
            c+=1
else:
    listxyz =np.zeros([x*y*z,],dtype=np.int)
    c = 0
    for i in range(0,x*y):
        for j in range(0,z):
            listxyz[c] = listxy[i]+listz[j]
            c+=1

listxyz=sorted(listxyz,reverse=True)

for i in range(0,k):
    print(listxyz[i])

### FIXED CODE ###

X,Y,Z,K = map(int,input().split())

A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

A.sort(reverse=True)
A = A[0:K]
B.sort(reverse=True)
B = B[0:K]
AB = [a+b for a in A for b in B]

AB.sort(reverse=True)

AB = AB[0:K]

C.sort(reverse=True)
C=C[0:K]
ABC = [ab+c for ab in AB for c in C]

ABC.sort(reverse=True)

for i in range(K):
    print(ABC[i])
### BUGGY CODE ###

k,q=map(int,input().split())
D=list(map(int,input().split()))
A=[]
for i in range(q):
    n,x,m=map(int,input().split())
    mD=list(map(lambda i: i%m, D)) #元の列のmodを取る
    ans=0
    cnt=x%m
    for d in mD[:((n-1)%k)]: #mod kで余る部分
        if d==0:
            ans+=((n-1)//k)+1
        cnt+=d*(((n-1)//k)+1)
    for d in mD[((n-1)%k):]: #余らない部分
        if d==0:
            ans+=((n-1)//k)
        cnt+=d*((n-1)//k)

    ans+=cnt//m
    A.append(n-1-ans)
for a in A:
    print(a)

### FIXED CODE ###

import sys
input = sys.stdin.readline

k,q=map(int,input().split())
D=list(map(int,input().split()))
A=[]
for i in range(q):
    n,x,m=map(int,input().split())
    mD=list(map(lambda i: i%m, D)) #元の列のmodを取る
    ans=0
    cnt=x%m
    a=(n-1)//k
    b=(n-1)%k
    for d in mD[:b]: #mod kで余る部分
        if d==0:
            ans+=a+1
        cnt+=d*(a+1)
    for d in mD[b:]: #余らない部分
        if d==0:
            ans+=a
        cnt+=d*a
    ans+=cnt//m
    print(n-1-ans)
### BUGGY CODE ###

#整数Nを入力
x = input()
N = int(x)

#N番目のリュカ数を返す関数を定義
def lucas(N):
  if N == 0:
    return 2
  elif N == 1:
    return 1
  return lucas(N-1) + lucas(N-2)

#N番目のリュカ数を出力
if 1<=N<=86:
    LN = lucas(N)
    print(LN)

### FIXED CODE ###

x = input()
N = int(x)

a = 2
luca = 1

for i in range(1,N):
  c = luca
  luca = a+luca
  a = c
  
print(luca)
### BUGGY CODE ###

s = list(input())
ans = 0
while True:
    n = len(s)
    if n <= 1:
        print(ans)
        exit()
    for i in range(n-1):
        if s[i] != s[i+1]:
            del s[i]
            del s[i]
            ans += 2
            break
        if i == n-2:
            print(ans)
            exit()


### FIXED CODE ###

from collections import Counter
s = list(input())
s = Counter(s)
print(min(s['0'], s['1']) * 2)
### BUGGY CODE ###

import copy
n = int(input())
a = list(map(int,input().split()))
ans = 1
if len(a) == 2:
  print(max(a))
else:
  for i in range(n):
    b = copy.deepcopy(a)
    b.pop(i)
    b.sort
    b0 = b[0]
    for j in range(1,n-1):
      b1 = b[j]
      r = 0
      while True:
        r = b1 % b0
        if r == 0:
          break
        elif r > b0:
          b1, b0 = r, b0
        else:
          b1, b0 = b0, r
    if b0 > ans:
      ans = b0
  print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort()
ans = 1
if n == 2:
  print(max(a))
else:
  a0 = a[0]
  a1 = a[1]
  r = 0
  while True:
    r = a1 % a0
    if r == 0:
      b0 = a0
      break
    elif r > a0:
      a1, a0 = r, a0
    else:
      a1, a0 = a0, r
  a1 = a[1]
  a2 = a[2]
  r = 0
  while True:
    r = a2 % a1
    if r == 0:
      b1 = a1
      break
    elif r > a1:
      a2, a1 = r, a1
    else:
      a2, a1 = a1, r
  a0 = a[0]
  a2 = a[2]
  r = 0
  while True:
    r = a2 % a0
    if r == 0:
      b2 = a0
      break
    elif r > a0:
      a2, a0 = r, a0
    else:
      a2, a0 = a0, r
  max_a = max(b0,b1,b2)
  kouho = []
  for j in range(max_a,1,-1):
    if max_a % j == 0:
      c = list(map(lambda x: x % j,a))
      c_ng = [i for i in c if i > 0]
    #print("j=",j,"c=",c,"c_ng=",c_ng)
      if len(c_ng) <= 1:
        ans = j
        break
  print(ans)
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
a = [input() for _ in range(h)]

q = deque()
done = set()
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            q.append((i, j, 0))
            done.add((i, j))

while q:
    i, j, k = q.popleft()
    done.add((i, j))
    if i > 0 and (i - 1, j) not in done:
        q.append((i - 1, j, k + 1))
    if i < h - 1 and (i + 1, j) not in done:
        q.append((i + 1, j, k + 1))
    if j > 0 and (i, j - 1) not in done:
        q.append((i, j - 1, k + 1))
    if j < w - 1 and (i, j + 1) not in done:
        q.append((i, j + 1, k + 1))

print(k)


### FIXED CODE ###

import numpy as np
from scipy.ndimage.morphology import distance_transform_cdt

h, w = map(int, input().split())
a = [input() for _ in range(h)]

a = np.array([[(ai[j] != "#") for j in range(w)] for ai in a])
d = distance_transform_cdt(a, metric="taxicab").max()
print(d)
### BUGGY CODE ###

n,m=[int(i) for i in input().split()]
a=[int(input()) for _ in range(m)]
dp=[1]+[0]*100010
for i in range(1,n+1):
    if i in a:
        dp[i]=0
    else:
        try:
            dp[i]=dp[i-1]+dp[i-2]
        except:
            dp[i]=dp[i-1]
print(dp[n]%1000000007)

### FIXED CODE ###

n,m=[int(i) for i in input().split()]
a=[int(input()) for _ in range(m)]
dp=[1]+[1]*100010
for i in a:
    dp[i]=0
for i in range(2,n+1):
    if dp[i]:
        dp[i]=dp[i-1]+dp[i-2]
print(dp[n]%1000000007)
### BUGGY CODE ###

n,a = int(input()),1
for i in range(n):
    a *= i+1
print(a%(10**9+7))

### FIXED CODE ###

n,a = int(input()),1
for i in range(n):
    a = a*(i+1)%(10**9+7)
print(a)
### BUGGY CODE ###

#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math

import itertools

#import bisect

import copy


def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

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

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

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

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]



def main():
    h,n=map(int,input().split()) #n yen, m types
    a=[]
    b=[]
    for i in range(n):
        x,y=map(int,input().split())
        a.append(x)
        b.append(y)

    dp=[INFI for i in range(h+1)]
    dp[0]=0
    for i in range(n):
        for j in range(len(dp)):
            if j-a[i]<0:
                dp[j] = min(dp[j], dp[0] + b[i])
            else:
                dp[j]=min(dp[j],dp[j-a[i]]+b[i])

    print(dp[h])


if __name__ == "__main__":
    main()

### FIXED CODE ###

#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
 
import itertools
 
#import bisect
 
import copy
 
 
def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
 
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
 
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
 
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
 
    return result
 
def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta
 
def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default
 
#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]
 
 
 
def main():
    h,n=map(int,input().split()) #n yen, m types
    a=[]
    b=[]
    for i in range(n):
        x,y=map(int,input().split())
        a.append(x)
        b.append(y)
 
    dp=[INFI for i in range(h+1)]
    dp[0]=0
    for i in range(n):
        for j in range(len(dp)):
            if j-a[i]<0:
                dp[j] = min(dp[j], dp[0] + b[i])
            else:
                dp[j]=min(dp[j],dp[j-a[i]]+b[i])
 
    print(dp[h])
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

# coding: utf-8
# Your code here!
N,K=map(int,input().split())

l=list(map(int,input().split()))
new=[]

for i in range(N):
    for j in range(i+1,N):
        if l[i]-l[j]==K:
            print("POSSIBLE")
            break
        new.append(abs(l[i]-l[j]))

Key=True

try:
    while Key:
        temp=[]
        for i in range(len(l)):
            for j in range(len(new)):
                if l[i]-new[j]==K:
                    print("POSSIBLE")
                    Key=False
                    break
                temp.append(abs(l[i]-new[j]))
        l=l+new
        new.clear()
        new+=temp
except TimeoutError:
    print("IMPOSSIBLE")
    



'''
while Key:
    print(new)
    temp=[]
    for i in range(len(l)):
        for j in range(len(new)):
            if l[i]-new[j]==K:
                print("POSSIBLE")
                Key=False
                break
            temp.append(abs(l[i]-new[j]))
    l=l+new
    new.clear()
    new+=temp
'''
            

    
    

### FIXED CODE ###

# coding: utf-8
# Your code here!
from fractions import gcd
from functools import reduce

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

if max(l)<K:
    print("IMPOSSIBLE")
else:
    if K%reduce(gcd, l)==0:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
### BUGGY CODE ###

import math
k = int(input())
s = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            s += math.gcd(a,math.gcd(b,c))
print(s)

### FIXED CODE ###

import math
k = int(input())
s = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            s += math.gcd(a,math.gcd(b,c))
print(s)
### BUGGY CODE ###

import itertools
import sys

input = sys.stdin.readline

maxn = 10000000000

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.append(-maxn)
B.append(-maxn)
C.append(-maxn)

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

apos, bpos, cpos = 0, 0, 0

while (apos + 1) * (bpos + 1) * (cpos + 1) < min(2 * 10 ** 6, X * Y * Z):
    if (
        apos < len(A) - 2
        and abs(A[apos] - A[apos + 1]) < abs(B[bpos] - B[bpos + 1])
        and abs(A[apos] - A[apos + 1]) < abs(C[cpos] - C[cpos + 1])
    ):
        apos += 1
    elif bpos < len(B) - 2 and B[bpos] - B[bpos + 1] < C[cpos] - C[cpos + 1]:
        bpos += 1
    else:
        cpos += 1

res = []
for a in list(itertools.product(A[: apos + 1], B[: bpos + 1], C[: cpos + 1])):
    res.append(a[0] + a[1] + a[2])

res.sort(reverse=True)
for k in range(K):
    print(res[k])


### FIXED CODE ###

import itertools
import sys

input = sys.stdin.readline

maxn = 10000000000

X, Y, Z, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)

cand = []
for i, a in enumerate(A):
    for j, b in enumerate(B):
        for k, c in enumerate(C):
            if (i + 1) * (j + 1) * (k + 1) <= K:
                cand.append(a + b + c)
            else:
                break

cand.sort(reverse=True)
for k in range(K):
    print(cand[k])
### BUGGY CODE ###

q = int(input())

for k in range(q):
    x = input()
    y = input()
    lcs = [0 for i in range(len(x)+1)] 
    for i in range(1,len(y) + 1):
        lcs_2 = lcs[:]
        for j in range(1,len(x) + 1):
            if x[j-1] == y[i-1]:
                lcs[j] = lcs_2[j-1] + 1  
            elif lcs[j] < lcs[j-1]:
                lcs[j] = lcs[j-1]
    print(lcs[len(x)])

### FIXED CODE ###

q = int(input())
 
def lcss(x,y):
     
    lcs = [0]*(len(x)+1)
    for i in range(len(y)):
        w1 = y[i]
        lcs_2 = lcs[:]
        for j in range(len(x)):
            if x[j] == w1:
                lcs[j+1] = lcs_2[j] + 1  
            elif lcs[j+1] < lcs[j]:
                lcs[j+1] = lcs[j]
    return lcs[-1]
 
for i in range(q):
    x = input()
    y = input()
    print(lcss(x,y))