Harryxun/stf_run huggingface dataset:
n, m, k = map(int, input().split())


class Combination:
    """
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv


mod = 998244353
total = 0
comb = Combination(n-1, mod)

v2 = [0] * (k+1)
v2[k] = (m * pow(m-1, n-k-1, mod)) % mod
for i in range(k-1, -1, -1):
    v2[i] = (v2[i+1] * (m-1)) % mod

for i in range(k+1):
    v = comb(n-1, i)
    total += (v * v2[i]) % mod
    total %= mod

print(total)

### FIXED CODE ###

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


class Combination:
    """
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv


mod = 998244353
total = 0
comb = Combination(n, mod)

v2 = [0] * (k+1)
v2[k] = (m * pow(m-1, n-k-1, mod)) % mod
for i in range(k-1, -1, -1):
    v2[i] = (v2[i+1] * (m-1)) % mod

for i in range(k+1):
    v = comb(n-1, i)
    total += (v * v2[i]) % mod
    total %= mod

print(total)
S = input()
k = []
b = ["A","C","G","T"]
a = 0
for i in range(len(S)):
    #len(S)の間roop
    #S[i]が"A" "C" "G" "T"のいずれかであるかを判定
    if S[i] in b:
        if i == len(S)-1:
            k.append(1)
            break
        else:
            for j in range(len(S)-1):
                if S[i+j] in b:
                    a += 1
                else:
                    k.append(a)
                    a = 0
                    break
print(max(k))

### FIXED CODE ###

S = input()
mode = 0
now = 0
k = []
for i in range(len(S)):
    if str(S[i]) == "A" or str(S[i]) == "T" or str(S[i]) == "G" or str(S[i]) == "C":
        if mode == 0:
            mode = 1
            now += 1
        else:
            now += 1
    else:
        k.append(now)
        now = 0
        mode = 0
k.append(now)
if len(k) == 0:
    print(0)
else:
    print(max(k))
AB = map(int, input().split())
S = list(map(str, input().split(-)))
ans = "No"
if AB[0] == len(S[0]):
    if AB[1] == len(S[1]):
        ans = "Yes"
print(ans)

### FIXED CODE ###

A, B = map(int, input().split())
S = list(map(str, input().split("-")))
ans = "No"
if A == len(S[0]):
    if B == len(S[1]):
        ans = "Yes"
print(ans)
s = input()
t = input()
count = 0
for k in range(a):
  if s[k] != t[k]:
    count += 1
    
print(count)

### FIXED CODE ###

s = input()
t = input()
count = 0
for k in range(len(s)):
  if s[k] != t[k]:
    count += 1
    
print(count)
N = int(input())
ans = 0
for i in range(1, N + 1):
	if len(str(i)) % 2 == 1:
		ans += 1
print(ans)

### FIXED CODE ###

a,b,c=map(int,input().split())
s=c-min(c,a-b)
print(s)
s = list(input())
arufa = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
for i in s:
    arufa.remove(i)
if arufa == []:
    dum = sorted(s,reverse=1)
    if dum == s:
        print(-1)
    else:
        arufa.append(s.pop(-1))
        for i in range(27):
            arufa.sort()
            if s[-1] < arufa[0]:
                s.pop(-1)
                s.append(arufa[0])
                break
            #for j in range(len(arufa)):
            #    if s[-1] < arufa[i]:
            #        s.append(arufa[0])
            #        print("".join(s))
            #        exit()
            arufa.append(s.pop(-1))
        print("".join(s))

else:
    s.append(arufa[0])
    print("".join(s))


### FIXED CODE ###

s = list(input())
kouho = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v",
         "w", "x", "y", "z"]
for i in s:
    kouho.remove(i)
if kouho == []:
    kouho.append(s.pop(-1))
    for i in range(25):
        dum = s.pop(-1)
        for j in range(len(kouho)):
            if dum < kouho[j]:
                s.append(kouho[j])
                print("".join(s))
                exit()
        else:
            kouho.append(dum)
            kouho.sort()
    else:
        print(-1)
    print("".join(s))
else:
    s.append(kouho[0])
    print("".join(s))
import numpy as np
import functools
import math
import scipy
import fractions
import itertools

def solve():
    n = int(input())
    x, l = [0]*n, [0]*n
    for i in range(n):
        x[i], l[i] = map(int, input().split())
    hoge = []
    for i in range(n):
        hoge.append(x+l)
    t = 0
    for i in range(n):
        if t < hoge[i]:
            ans += 1
    print(ans)
    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import numpy as np
import functools
import math
import scipy
import fractions
import itertools

def solve():
    n = int(input())
    x, l = [0]*n, [0]*n
    for i in range(n):
        x[i], l[i] = map(int, input().split())
    hoge = []
    for i in range(n):
        hoge.append([x[i]+l[i], x[i]-l[i]])
    hoge.sort()
    t = -1000000000000000000000
    ans = 0
    for i in range(n):
        if t <= hoge[i][1]:
            ans += 1
            t = hoge[i][0]
    print(ans)
    return 0

if __name__ == "__main__":
    solve()
import math
n = int(input())
prime_list = []
    #2からnまでの数字をsearch_listに入れる
search_list = list(range(2,n+1))
while True:
      #search_listの先頭の値が√nの値を超えたら処理終了
      if search_list[0] > math.sqrt(n):
        #prime_listにsearch_listを結合
          prime_list.extend(search_list)
          break
      else:
        #search_listの先頭をprime_listに入れる
          head_num = search_list[0]
          prime_list.append(head_num)
        #search_listの先頭をpopする
          search_list.pop(0)
        #head_numの倍数を取り除く
          search_list = [num for num in search_list if num % head_num != 0]
#print(prime_list)
########ここから本問を解く#########
ans = 1
for x in prime_list:
  tmp = 0
  nl = 1
  while(x**nl <= n):
    tmp += n//(x**nl)
    nl += 1
  ans *= tmp+1
if ans >= 10**9+7:
  ans %= (10**9+7)
print(ans)

### FIXED CODE ###

import sys
import math
n = int(input())
if n == 1:
  print(1)
  sys.exit()
prime_list = []
    #2からnまでの数字をsearch_listに入れる
search_list = list(range(2,n+1))
while True:
      #search_listの先頭の値が√nの値を超えたら処理終了
      if search_list[0] > math.sqrt(n):
        #prime_listにsearch_listを結合
          prime_list.extend(search_list)
          break
      else:
        #search_listの先頭をprime_listに入れる
          head_num = search_list[0]
          prime_list.append(head_num)
        #search_listの先頭をpopする
          search_list.pop(0)
        #head_numの倍数を取り除く
          search_list = [num for num in search_list if num % head_num != 0]
#print(prime_list)
########ここから本問を解く#########
ans = 1
for x in prime_list:
  tmp = 0
  nl = 1
  while(x**nl <= n):
    tmp += n//(x**nl)
    nl += 1
  ans *= tmp+1
if ans >= 10**9+7:
  ans %= (10**9+7)
print(ans)
N = int(input())
A = int(input())
B = int(input())

if N == 1:
    print("Hello World")
else:
    print(A+B)

### FIXED CODE ###

N = int(input())
if N == 1:
  print("Hello World")
else:
  A = int(input())
  B = int(input())
  print(A+B)
def gcd(a, b):
	if b == 0: return a
	return gcd(b, a%b)

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

A = []

N = int(raw_input())
A = map(int, raw_input().split())
l = 1
for x in A:
    l = lcm(l, x)
ans, mod = 0, 1000000007
for x in A:
    ans = (ans + l/x)
    if ans > mod: ans = ans % mod
print(ans)


### FIXED CODE ###

def gcd(a,b):
    if not b: return a
    return gcd(b,a%b)

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

N = int(input())
A = list(map(int,input().split()))
l = 1
ans, mod = 0, 1000000007

for x in A:
    l = lcm(l, x)

for x in A:
    ans = ans + l//x
print(ans % mod)
c = 0
while True:
    x = int(input())
    if x == 0;
        break;

    c += 1
    print('Case', str(c) + ':', x)

### FIXED CODE ###

c = 0
while True:
    x = int(input())
    if x == 0:
        break;

    c += 1
    print('Case', str(c) + ':', x)
import numpy as np
mod = 10**9 + 7


def solve(now, from_, K, pa, b):
    if from_ == -1:
        can_num = K - 1
    else:
        can_num = K - 2
    if K < pa[now + 1] - pa[now]:
        return 0
    case_num = 1
    for i in range(pa[now], pa[now + 1]):
        if b[i] != from_:
            case_num *= can_num
            can_num -= 1
            case_num %= mod
    for i in range(pa[now], pa[now + 1]):
        if b[i] != from_:
            case_num *= solve(b[i], now, K, pa, b)
            case_num %= mod
    return case_num


def main():
    N, K = map(int, input().split())
    ab = np.array([list(map(int, input().split())) for _ in range(N - 1)], dtype=np.int32)
    ab = (ab - 1).T
    ab = np.hstack((ab, ab[[1, 0]]))
    ab = ab[:, np.argsort(ab[0])]
    pa = np.unique(ab[0], return_index=True)[1]
    pa = np.append(pa, 2 * (N - 1))
    ans = K * solve(0, -1, K, pa, ab[1])
    print(ans % mod)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
mod = 10**9 + 7


def solve(now, from_, K, ab):
    if from_ == -1:
        can_num = K - 1
    else:
        can_num = K - 2
    if K < len(ab[now]):
        return 0
    case_num = 1
    for i in ab[now]:
        if i != from_:
            case_num *= can_num
            can_num -= 1
            case_num %= mod
    for i in ab[now]:
        if i != from_:
            case_num *= solve(i, now, K, ab)
            case_num %= mod
    return case_num


def main():
    N, K = map(int, input().split())
    if N == 1:
        print(K)
        exit(0)
    ab = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        ab[a - 1].append(b - 1)
        ab[b - 1].append(a - 1)
    ans = K * solve(0, -1, K, ab)
    print(ans % mod)


if __name__ == "__main__":
    main()
n, m, X, Y = map(int, input().split())
xs = list(map(int, input().split()))
ys = list(map(int, input().split()))
x_max = max(xs)
y_min = min(ys)
if y_min > x_max:
    for z in list(range(x_max, y_min + 1)):
        if (z > X) and (z <= Y):
            print('No War')
            break
    else:
        print('War')
else:
    print(bvv)

### FIXED CODE ###

n, m, X, Y = map(int, input().split())
xs = list(map(int, input().split()))
ys = list(map(int, input().split()))
x_max = max(xs)
y_min = min(ys)
def get_war(x_max, y_min, X, Y):
    if y_min > x_max:
        for z in list(range(x_max+1, y_min + 1)):
            if (z > X) and (z <= Y):
                return 'No War'
            else:
                pass
        else:
            return 'War'
    else:
        return 'War'
print(get_war(x_max, y_min, X, Y))
import sys

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

for x in range(n-1)
  	if nums[x] > nums[x+1]:
    	nums[x] -= 1

    if nums[x] > nums[x+1]:
      	print('No')
      	sys.exit()

print('Yes')

### FIXED CODE ###

import sys
 
n = int(input())
nums = list(map(int, input().split()))
maxnum = 0

for x in range(n):
    if maxnum < nums[x]:
        maxnum = nums[x]
    if maxnum - nums[x] > 1:
        print('No')
        sys.exit() 
 
print('Yes')
n=int(input())
a=list(map(int,input().split()))
o=[]
e=[]
for i in range(n):
  if i%2==0:
    o.append(a[i])
  else:
    e.append(a[i])
from collections import Counter as co
o=co(o)
e=co(e)
ov=o.values()
ev=e.values()
mo=max(ov)
me=max(ev)
if n==2:
  if a[0]==a[1]:
    print(1)
  else:
    print(0)
else:
  if max(o,key=o.get)==max(e,key=e.get):
    if mo>me:
      me=sorted(ev)[n//2-2]
    else:
      mo=sorted(ov)[n//2-2]
  print(n-mo-me)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
o=[]
e=[]
for i in range(n):
  if i%2==0:
    o.append(a[i])
  else:
    e.append(a[i])
from collections import Counter as co
o=co(o)
e=co(e)
o['x']=0
e['x']=0
ov=o.values()
ev=e.values()
mo=max(ov)
me=max(ev)
if n==2:
  if a[0]==a[1]:
    print(1)
  else:
    print(0)
else:
  if max(o,key=o.get)==max(e,key=e.get):
    if mo>me:
      me=sorted(ev)[-2]
    elif mo<me:
      mo=sorted(ov)[-2]
    else:
      mo=max(sorted(ev)[-2],sorted(ov)[-2])
  print(n-mo-me)
N = int(raw_input())
s = [int(raw_input()) for _ in range(N)]

flag = True
for i in range(len(s)):
    if (s[i] % 10) != 0:
        flag = False
        break
if flag:
    print(0)
else:
    s.sort()
    s = s[::-1]
    Ncombination = 2**len(s)

    for c in range(Ncombination):
        SUM = 0
        combination = format(c, 'b').zfill(len(s))
        # print("combination", combination)
        for i in range(len(s)):
            # print("combination", i, combination[i])
            if combination[i] == "0":
                SUM += s[i]
        # print("SUM", SUM)
        if (SUM % 10) != 0:
            break
    print(SUM)
~                

### FIXED CODE ###

N = int(raw_input())
s = [int(raw_input()) for _ in range(N)]

result = sum(s)
if (result % 10) != 0:
    print(result)
else:
    s.sort()
    for i in range(len(s)):
        if (s[i] % 10) != 0:
            result -= s[i]
            break
    if (result % 10) != 0:
        print(result)
    else:
        print(0)
import sys, math
from collections import defaultdict
def input(): return sys.stdin.readline().strip()


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit < p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


def main():
    N = int(input())
    table = get_sieve_of_eratosthenes(N)
    #print(table)
    primes = defaultdict(int)
    for n in range(2, N + 1):
        for p in table:
            cnt = 0
            while n % p == 0:
                n //= p
                cnt += 1
            primes[p] += cnt
    #print(primes)
    
    over_3 = 0
    over_5 = 0
    over_15 = 0
    over_25 = 0
    over_75 = 0
    for p in primes:
        if primes[p] >= 2: over_3 += 1
        if primes[p] >= 4: over_5 += 1
        if primes[p] >= 14: over_15 += 1
        if primes[p] >= 24: over_25 += 1
        if primes[p] >= 74: over_75 += 1
    #print(over_3)
    #print(over_5)
    #print(over_15)
    #print(over_25)
    #print(over_75)
    
    val1 = over_5 * (over_5 - 1) * (over_3 - 2) // 2
    val2 = over_15 * (over_5 - 1)
    val3 = over_25 * (over_3 - 1)
    print(val1 + val2 + val3 + over_75)

    




if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys, math
from collections import defaultdict
def input(): return sys.stdin.readline().strip()


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit < p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


def main():
    N = int(input())
    if N < 10:
        print(0)
        return
    table = get_sieve_of_eratosthenes(N)
    #print(table)
    primes = defaultdict(int)
    for n in range(2, N + 1):
        for p in table:
            cnt = 0
            while n % p == 0:
                n //= p
                cnt += 1
            primes[p] += cnt
    #print(primes)
    
    over_3 = 0
    over_5 = 0
    over_15 = 0
    over_25 = 0
    over_75 = 0
    for p in primes:
        if primes[p] >= 2: over_3 += 1
        if primes[p] >= 4: over_5 += 1
        if primes[p] >= 14: over_15 += 1
        if primes[p] >= 24: over_25 += 1
        if primes[p] >= 74: over_75 += 1
    #print(over_3)
    #print(over_5)
    #print(over_15)
    #print(over_25)
    #print(over_75)
    
    val1 = over_5 * (over_5 - 1) * (over_3 - 2) // 2
    val2 = over_15 * (over_5 - 1)
    val3 = over_25 * (over_3 - 1)
    print(val1 + val2 + val3 + over_75)

    




if __name__ == "__main__":
    main()
N = input()

if N >= 1000:
    print( 'ABD' )

else :
    print( 'ABC' )


### FIXED CODE ###

N = int(input())

if N >= 1000:
    print( 'ABD' )

else :
    print( 'ABC' )
N, x = map(int, input().split())
A = [int(i) for i in input().split()]

A.sort()
ans = 0

for i in A:
    x -= a
    if x >= 0:
        ans += 1
    else:
        break
if x > 0:
    ans -= 1
print(ans)



### FIXED CODE ###

n, x = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
ans = 0
for a in A:
    x -= a
    if x >= 0:
        ans += 1
    else:
        break
if x > 0:
    ans -= 1
print(ans)
k,s = [int(i) for i in input().split()]
def a(n):
  if n == 1:
    return n
  else:
    return n + a(n-1)
  
if s <= k:
  print(a(s + 1))
elif s >= 2 * k and s <= 3 * k:
  print(a(3 * k - s + 1))
elif s > k and s < 2 * k:
  print(a(s + 1) - 3 * a(s - k))
else:
  print(0)

### FIXED CODE ###

k,s = [int(i) for i in input().split()]
def a(n):
  return int(n * (n + 1) / 2)
  
if s <= k:
  print(a(s + 1))
elif s >= 2 * k and s <= 3 * k:
  print(a(3 * k - s + 1))
elif s > k and s < 2 * k:
  print(a(s + 1) - 3 * a(s - k))
else:
  print(0)
import fractions

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

def lcm(x, y):
    return int((x * y) / fractions.gcd(x, y))

def num_of_mod0(mod):
    if A%mod == 0:
        start = A
    else:
        start = (int(A/mod) +1) * mod

    end = (int(B /mod)) * mod

    return (end - start) / mod +1

ans =(B-A+1)-(num_of_mod0(C) + num_of_mod0(D)- num_of_mod0(lcm(C,D)))
ans = int(ans)
print(ans)

### FIXED CODE ###

S = str(input())

flag = False
for i in range(1,4):
    if S[i-1] ==S[i]:
        flag = True

if flag:
    print('Bad')
else:
    print('Good')
n = int(input())
if (n % 2 == 0):
  print("%.10f" % (1/2))
else:
  print("%.10f" % ((n//2)+1)/n)

### FIXED CODE ###

n = int(input())
if (n%2 == 0):
    print("%.10f" % (1/2))
else:
    ans = ((n//2) + 1) / n
    print("%.10f" % ans)
N, M = map(int, input().split())
p = []
y = []
for i in range(M):
    p1,y1=[int(i) for i in input().split()]
    p.append(p1)
    y.append(y1)
for idx in range(M):
    ans[idx] = [idx, p[idx], y[idx]]
ans = sorted(ans, key=lambda x: x[1])
ans = sorted(ans, key=lambda x: x[2])
for idx in range(M):
    if idx == 0:
        ans[idx][2] = 1
    else:
        if ans[idx][1] == ans[idx-1][1]:
            ans[idx][2] = ans[idx-1][2] + 1
        else:
            ans[idx][2] = 1
ans = sorted(ans, key=lambda x: x[0])
for idx in range(M):
    print('{:0=6}{:0=6}'.format(ans[idx][1], ans[idx][2]))

### FIXED CODE ###

N, M = map(int, input().split())
anses = [0] * M
pre = [0] * N
 
for idx in range(M):
    p, y = (int(x) for x in input().split())
    anses[idx] = [idx, p, y, 0]

anses = sorted(anses, key=lambda x: x[2])

for ans in anses:
    pre[ans[1]-1] += 1
    ans[3] = pre[ans[1]-1]

anses = sorted(anses, key=lambda x: x[0])

for ans in anses:
    print('{:0=6}{:0=6}'.format(ans[1], ans[3]))
N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
ans = 0
C = A + B
for i in range(len(C)):
  C[i] = min(A[i],B[i])
  
for i in range(len(C)):
  if K => C[i]:
    K -= C[i]
    ans +=1
  else:
    break
print(ans)
  	

### FIXED CODE ###

N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
a = [0]
b = [0]
for i in range(N):
  a.append(a[i] + A[i])
for i in range(M):
  b.append(b[i] + B[i])
  
ans = 0
j = M
for i in range(N+1):
  if a[i] > K:
    break
  while b[j] > K - a[i]:
    j -= 1
  ans = max(ans,i+j)
print(ans)
a,b=map(int(),input.split())
if a>9 or b>9 :
    print(-1)
else:
    print(a*b)

### FIXED CODE ###

a,b=map(int,input().split())
if a>9 or b>9 :
    print(-1)
else:
    print(a*b)
n,k=map(int,input().split())
list_a=[]
for d in range(k):
  d=int(input())
  a=list(map(int,input().split()))
  list_a.extend(a)
print(list_a)
ans=0
for i in range(1,n): 
 if list_a.count(i)==0:
      ans+=1
print(ans)
       

### FIXED CODE ###

n=str(input())
if n=="ABC":
  print("ARC")
else:
  print("ABC")
N, A, B, C = map(int, input().split())
l = [int(input()) for i in range(N)]


def dfs(cur, a, b, c):
    if cur == N:
        if min(a, b, c) > 0:
            return abs(a - A) + abs(b - B) + abs(c - C) - 30
        else:
            return float('inf')
    ret0 = dfs(cur + 1, a, b, c)
    ret1 = dfs(cur + 1, a + l[cur], b, c) + 10
    ret2 = dfs(cur + 1, a, b + l[cur], c) + 10
    ret3 = dfs(cur + 1, a, b, c + [cur]) + 10
    return min(ret0, ret1, ret2, ret3)


print(dfs(0, 0, 0, 0))


### FIXED CODE ###

N, A, B, C = map(int, input().split())
l = [int(input()) for i in range(N)]


def dfs(cur, a, b, c):
    if cur == N:
        if min(a, b, c) > 0:
            return abs(a - A) + abs(b - B) + abs(c - C) - 30
        else:
            return float('inf')
    ret0 = dfs(cur + 1, a, b, c)
    ret1 = dfs(cur + 1, a + l[cur], b, c) + 10
    ret2 = dfs(cur + 1, a, b + l[cur], c) + 10
    ret3 = dfs(cur + 1, a, b, c + l[cur]) + 10
    return min(ret0, ret1, ret2, ret3)


print(dfs(0, 0, 0, 0))
n = input()
answer = 1
for i in range(int(n)):
    a = int(input())
    answer = answer * a
    if answer > 10**18:
        print("-1")
    else:
        print(answer)

### FIXED CODE ###

a,b = input().split()
print(int(a) * int(b))
import sys


fin = sys.stdin.readline
N = int(fin())
s_list = [fin().rstrip("\n") for _ in range(N)]
num_AB_in_between = 0
s_Bhoge = 0
s_hogeA = 0
s_BA = 0
for s in s_list:
    if s[0] == "B" and s[-1] == "A":
        s_BA += 1
    elif s[0] == "B":
        s_Bhoge += 1
    elif s[-1] == "A":
        s_hogeA += 1

    for i, char in enumerate(s[:-1]):
        next_char = s[i + 1]
        if char == "A" and next_char == "B":
            num_AB_in_between += 1

# print(s_Bhoge, s_hogeA, s_BA)
if s_BA:
    num_AB_bound = 2 * s_BA - 2 + int(s_Bhoge > 0) + int(s_hogeA > 0)
    num_AB_bound += max(0, min(s_Bhoge - 1, s_hogeA - 1))
    # num_AB_bound += min(s_Bhoge - 1, s_hogeA - 1)
else:
    num_AB_bound = min(s_Bhoge, s_hogeA)
print(num_AB_in_between + num_AB_bound)


### FIXED CODE ###

N, K = [int(elem) for elem in input().split()]

print(N - K + 1)
Xs = raw_input()
  Ys = raw_input()
  count = 0
  a = 1

  for i in range(len(Ys) + 1):
    dp[0][i + 1] = Ys[i] 
  for j in range(len(Xs) + 1):
    dp[j + 1][0] = Xs[j]

  for i in range(1, len(Ys) + 1):
    for j in range(a + 1, len(Xs) + 1):
      if dp[j][0] == dp[i][1]:
         count = count + 1
         a = j
         break
    if dp[j][0] == dp[i][1]:
      break

   print count

### FIXED CODE ###

def solve_lcs():
    x = raw_input()
    y = raw_input()
 
    a = len(x)
    b = len(y)
    c1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = x[i]
        c2 = c1+[]
        for j in range(b):
            if e1 == y[j]:
                c1[j+1] = c2[j] + 1
            elif c1[j+1] < c1[j]:
                c1[j+1] = c1[j]
    return c1[-1]
 
n = input()
for i2 in range(n):
    print solve_lcs()