Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit(5000)


class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        if self.par[x] != x:
            self.par[x] = self.find(self.par[x]) # contraction
        return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if not self.same(x, y):
            self.size[y] += self.size[x]
        self.par[x] = y

    def same(self, x, y):
        return self.find(x) == self.find(y)


n, m = map(int, input().split())
edge = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]

uf = UnionFind(n)
ans = n * (n-1) // 2
anss = []
for i in reversed(range(m)):
    anss.append(ans)
    # print(uf.par)
    # print(uf.size, [uf.size[uf.find(i)] for i in range(n)])
    a, b = edge[i]
    if not uf.same(a, b):
        ans -= uf.size[uf.find(a)] * uf.size[uf.find(b)]
    # print(i, a, b)

    uf.unite(a, b)

for i in reversed(range(m)):
    print(anss[i])


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)


class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        if self.par[x] != x:
            self.par[x] = self.find(self.par[x]) # contraction
        return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if not self.same(x, y):
            self.size[y] += self.size[x]
        self.par[x] = y

    def same(self, x, y):
        return self.find(x) == self.find(y)


n, m = map(int, input().split())
edge = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]

uf = UnionFind(n)
ans = n * (n-1) // 2
anss = []
for i in reversed(range(m)):
    anss.append(ans)
    # print(uf.par)
    # print(uf.size, [uf.size[uf.find(i)] for i in range(n)])
    a, b = edge[i]
    if not uf.same(a, b):
        ans -= uf.size[uf.find(a)] * uf.size[uf.find(b)]
    # print(i, a, b)

    uf.unite(a, b)

for i in reversed(range(m)):
    print(anss[i])
a = input().split()
a = [int(i) for i in a]
c = input().split()
c = [int(i) for i in c]

def dacao(b):
	aller = [0]
	sumer = 0
	for i in b:
		sumer += i
		aller.append(sumer)
		
	superlist = dict()
	for i in range(len(b)):
		for j in range(i + 1, len(b) + 1):
			temp = bin(aller[j] - aller[i])[::-1]
			x = []
			for k in range(len(temp)):
				if temp[k] == '1':
					x.append(k)
			for m in x:
				try:
					superlist[m].append(aller[j] - aller[i])
				except:
					superlist[m] = [aller[j] - aller[i]]
				
	for i in sorted(superlist)[::-1]:
		if len(superlist[i]) >= a[1]:
			li = list(map(lambda x : x - 2**i, superlist[i]))
			return li, i
			break
		return [], -1
			
def cao(b):
	aller = [0]
	sumer = 0
	superlist = dict()
	for i in b:
		temp = bin(i)[::-1]
		x = []
		for k in range(len(temp)):
			if temp[k] == '1':
				x.append(k)
		for m in x:
			try:
				superlist[m].append(i)
			except:
				superlist[m] = [i]
				
	for i in sorted(superlist)[::-1]:
		if len(superlist[i]) >= a[1]:
			li = list(map(lambda x : x - 2**i, superlist[i]))
			return li, i
			break
		return [], -1

sumx = 0
gan1, gan2 = dacao(c)
while gan2 != -1:
	sumx += 2**gan2
	gan1, gan2 = cao(gan1)
	
print(sumx)

### FIXED CODE ###

a = input().split()
a = [int(i) for i in a]
b = input().split()
b = [int(i) for i in b]

def cao(aller, i):
	dicter = dict()
	for m in aller:
		for n in m:
			if n < i:
				try:
					dicter[n].append(m)
				except:
					dicter[n] = [m]
	for i in sorted(dicter)[::-1]:
		if len(dicter[i]) >= a[1]:
			return dicter[i], i
	return [], -1
	
aller = [0]
sumer = 0
for i in b:
	sumer += i
	aller.append(sumer)
	
superlist = dict()
for i in range(len(b)):
	for j in range(i + 1, len(b) + 1):
		temp = bin(aller[j] - aller[i])[::-1]
		x = []
		for k in range(len(temp)):
			if temp[k] == '1':
				x.append(k)
		for m in x:
			try:
				superlist[m].append(x)
			except:
				superlist[m] = [x]
						
for i in sorted(superlist)[::-1]:
	if len(superlist[i]) >= a[1]:
		li = superlist[i]
		sumer = 2 ** i
		gan1, gan2 = cao(li, i)
		while gan2 != -1:
			sumer += 2**gan2
			gan1,gan2 = cao(gan1,gan2)
		print(sumer)
		break
A,B,C=input().split()

if A[len(A)-1]==B[0] and B[len(B-1)]==C[0]:
  print('YES')
else:
  print('NO')

### FIXED CODE ###

A,B,C=input().split()

if A[len(A)-1]==B[0] and B[len(B)-1]==C[0]:
  print('YES')
else:
  print('NO')
# -*- coding: utf-8 -*-

if __name__ == '__main__':
    N = input()
    n0 = 2
    n1 = 1
    if N == 1:
        print(1)
    now = 1
    while now != N:
        n = n0 + n1
        n0 = n1
        n1 = n
        now += 1
    print(n)


### FIXED CODE ###

# -*- coding: utf-8 -*-

if __name__ == '__main__':
    N = input()
    n0 = 2
    n1 = 1
    if N == 1:
        print(1)
    else:    
        now = 1
        while now != N:
            n = n0 + n1
            n0 = n1
            n1 = n
            now += 1
        print(n)
h,w=map(int,input().split())

m=[input() for i in range(w)]


cnt=[[1000000 for i in range(h)]for j in range(w)]


if m[0][0]=="#":
    cnt[0][0]=1
else:
    cnt[0][0]=0

for y in range(w):
    for x in range(h):
        if x!=0:
            if m[y][x-1]=="." and m[y][x]=="#":
                cnt[y][x]=min(cnt[y][x],cnt[y][x-1]+1)
            else:
                cnt[y][x]=min(cnt[y][x],cnt[y][x-1])
        if y!=0:
            if m[y-1][x]=="." and m[y][x]=="#":
                cnt[y][x]=min(cnt[y][x],cnt[y-1][x]+1)
            else:
                cnt[y][x]=min(cnt[y][x],cnt[y-1][x])


print(1)

### FIXED CODE ###

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

m=[input() for i in range(h)]


cnt=[[1000000 for i in range(w)] for j in range(h)]

if m[0][0]=="#":
    cnt[0][0]=1
else:
    cnt[0][0]=0

for y in range(h):
    for x in range(w):
        if x>0:
            if m[y][x-1]=="." and m[y][x]=="#":
                cnt[y][x]=min(cnt[y][x],cnt[y][x-1]+1)
            else:
                cnt[y][x]=min(cnt[y][x],cnt[y][x-1])
        if y>0:
            if m[y-1][x]=="." and m[y][x]=="#":
                cnt[y][x]=min(cnt[y][x],cnt[y-1][x]+1)
            else:
                cnt[y][x]=min(cnt[y][x],cnt[y-1][x])


print(cnt[h-1][w-1])
n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
b=[]
for i in range(m):
    p=list(map(int,input().split()))
    b.append(p)
b.sort(key=lambda x:-x[1])
a.sort()
wes=-1
i=0
s=0
res=0
while i<m:
    wes+=b[i][0]
    if wes>n-1:
        res=1
        wes-=b[i][0]
        wes+=1
        break
    if a[wes]>=b[i][1]:
        wes-=b[i][0]
        wes+=1
        break
    else:
        s+=b[i][0]*b[i][1]
        i+=1
if i!=m:
    for j in range(b[i][0]):
        if a[wes+j]<b[i][1]:
            a[wes+j]=b[i][1]
    f=a[wes:]
    s+=sum(f)
else:
    s+=sum(a[wes+1:])
if res=1:
    j=n-1
    while j>=wes:
        if a[j]>b[i][1]:
            s+=a[j]
        else:
            s+=b[i][1]
        j-=1
        
print(s)

### FIXED CODE ###

n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
b=[]
s=0
for i in range(m):
    p=list(map(int,input().split()))
    b.append(p)
    s+=p[0]
b.sort(key=lambda x:-x[1])
a.sort()
if s>n:
    s=n
c=[]
i=0
sun=0
while sun<s:
    for j in range(b[i][0]):
        c.append(b[i][1])
    sun+=b[i][0]
    i+=1
for u in range(s):
    if a[u]<c[u]:
        a[u]=c[u]
    
print(sum(a))
N,M = map(int,input().split())
a = sorted(list(map(int,input().split())),reverse=True)

s = sum(a)

if a[M-1] / s >= 1/4M:
  print("Yes")
else:
  print("No")
  
return

### FIXED CODE ###

N,M = map(int,input().split())
a = sorted(list(map(int,input().split())),reverse=True)
a
s = sum(a)

if a[M-1] >= s/(4*M):
  print("Yes")
else:
  print("No")
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
def solve_binary(mid,j):
    return pairs[mid][0] >= j
    pass

def binary_search(n,j):
    ok=n
    ng=0
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if solve_binary(mid,j):
            ok=mid
        else:
            ng=mid
    return ok

n = int(input())
C = [int(input()) for i in range(n)]
pairs = []
data = [-1]*(n+1)
for i,ci in enumerate(C):
  if data[ci] != -1 and abs(i-data[ci]) != 1:
    pairs.append((data[ci],i))
  data[ci] = i
pairs.sort()
l = len(pairs)
for i,j in pairs:
  k = binary_search(l,j)
  # print(k,12345)
  ans += l-k+1
  ans %= mod
print(ans+1)
# print(pairs)






### FIXED CODE ###

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
C = [int(input()) for i in range(n)]
pairs = [-1]*(n+1)
data = [-1]*(2*10**5+1)
for i,ci in enumerate(C):
  if data[ci] != -1 and abs(i-data[ci]) != 1:
    pairs[data[ci]] = i
  data[ci] = i
imos = [0] * (n+1)
for i in range(n-1,-1,-1):
  # ペアを持たないとき
  if pairs[i] == -1:
    imos[i] = imos[i+1]
    # print(i,imos[i],imos[i+1])
  else:
    j = pairs[i]
    imos[i] = imos[i+1] + imos[j] + 1
    imos[i] %= mod
  # ans += imos[i] + imos[j]
  # ans %= mod
  # imos[i-1] += imos[i]
print((imos[0]+1)%mod)
# print((ans+1)%mod)
# print(imos)
s = input()
print(sum(s[:i].count("B") for i in range(len(s)) if s[i]=="W")

### FIXED CODE ###

c = b = 0
for s in input():
  c += b*(s=="W")
  b += s=="B"
print(c)
n=int(input())
s=input()
ans=len(s)
def check(m):
  a=len(m)
  if a%2==1:
    return False
  else:
    if s[0:m//2]==s[m//2:m]:
      return True
    else:
      return False
for i in range(1,len(s),-1):
  ans-=1
  if check(s[0:i])==True:
    print(ans)
  


### FIXED CODE ###

s=input()
ans=len(s)
def check(m):
  a=len(m)
  if a%2==1:
    return False
  else:
    if s[0:a//2]==s[a//2:a]:
      return True
    else:
      return False
for i in range(len(s)-1,0,-1):
  ans-=1
  if check(s[0:i])==True:
    print(ans)
    break
def solution(a):
    A = a[0]
    B = sum(a) - a[0]
    Min = abs(A - B)
    for i in xrange(1, len(a)-1):
        A += a[i]
        B -= a[i]
        if Min > abs(A- B):
            Min = abs(A - B)
    print Min
import math
N = int(raw_input())
a = map( int, raw_input().split())
solution(a)

### FIXED CODE ###

a,b =map( int, raw_input().split())
if a%3 == 0 or b%3 == 0 or (a+b)%3 == 0:
    print 'Possible'
else:
    print 'Impossible'
from functools import reduce
from math import gcd

n=int(input())
a_s=list(map(int,input().split()))
mx=0
for i in range(n):
    b=a_s[:i]+a_s[i+1:]
    g=reduce(gcd,b)
    if g>mx:
        mx=g
print(mx)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

def Lgcd(i):
    if i == 0:
        return 0
    if i == 1:
        return a_s[0]
    if i in Lmemo:
        return Lmemo[i]
    re = gcd(Lgcd(i - 1), a_s[i - 1])
    Lmemo[i] = re
    return re


def Rgcd(i):
    if i == n - 1:
        return 0
    if i == n - 2:
        return a_s[-1]
    if i in Rmemo:
        return Rmemo[i]
    re = gcd(Rgcd(i + 1), a_s[i + 1])
    Rmemo[i] = re
    return re


def gcd(a, b):
    if a * b == 0:
        return a + b
    while 1:
        a, b = b, a % b
        if b == 0:
            return a


Lmemo = {}
Rmemo = {}
n = int(input())
a_s = list(map(int, input().split()))
mx = 0
for i in range(n):
    g = gcd(Lgcd(i),Rgcd(i))
    if g > mx:
        mx = g
print(mx)
# -*- coding: utf-8 -*-

# 整数の入力
N = int(input())
# スペース区切りの整数の入力
#b, c = map(int, input().split())
l = list(map(int, input().split()))
max = max(l)
#for i in l:
#    print(i)

num = 0
for i in l:
    num=i+num
num = num-max
print(num)
print(max)
if num >= max:
    print("Yes")
else:
    print("No")
# 文字列の入力
#s = input()
# 出力
#print("{} {}".format(a+b+c, s))

### FIXED CODE ###

# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
#1 <= T,X <= 100
T, X = map(float, input().split())
# 文字列の入力
#s = input()
t = T / X
# 出力
print(t)
#print("{} {}".format(a+b+c, s))
N,M,C = list(map(int,input().split()))
import numpy as np
B = np.array(input().split() ,dtype=np.int64)
ret  =0
for i in range(N):
    if( np.sum(np.matmul(B , np.array(input().split() ,dtype=np.int64))) +C>0):
        ret += 1
print(ret)

### FIXED CODE ###

N,M,C = list(map(int,input().split()))
import numpy as np
B = np.array(input().split() ,dtype=np.int64)
ret =0
for i in range(N):
    if( np.sum(B * np.array(input().split() ,dtype=np.int64)) +C>0):
        ret += 1
print(ret)
c=int(input())
if c in "aiueo":
    print("vowel")
else:
    print("consonant")

### FIXED CODE ###

print("vowel" if input() in "aiueo" else "consonant")
def main():
    n,m,q=map(int,input().split())
    ABCD=[list(map(int,input().split())) for _ in range(q)]
    ans=0
    L=list(range(1,m+1))
    for Q in combinations_with_replacement(L,n):
        Q=list(sorted(Q))
        tmp=0
        for a,b,c,d in ABCD:
            if Q[b-1]-Q[a-1]==c:
                tmp+=d
        ans=max(ans,tmp)
    print(ans)
    
if __name__=='__main__':
    main()

### FIXED CODE ###

from itertools import combinations_with_replacement
def main():
    n,m,q=map(int,input().split())
    ABCD=[list(map(int,input().split())) for _ in range(q)]
    ans=0
    L=list(range(1,m+1))
    for Q in combinations_with_replacement(L,n):
        Q=list(sorted(Q))
        tmp=0
        for a,b,c,d in ABCD:
            if Q[b-1]-Q[a-1]==c:
                tmp+=d
        ans=max(ans,tmp)
    print(ans)
    
if __name__=='__main__':
    main()
import sys
input = sys.stdin.readline
mod = 10**9 + 7
n = int(input())
ab = [[int(x) for x in input().split()] for _ in range(n)]
from collections import defaultdict, Counter
import math

double_zero_cnt = 0 # [0, 0]の個数
a_b = [] # a/bを、約分した形で保持(a/gcd(a, b), b/gcd(a, b), 符号)
for a, b in ab:
    if a == 0 and b == 0: 
        double_zero_cnt += 1
        continue
    g = math.gcd(a, b)
    a //= g
    b //= g
    sign = 1 if a*b > 0 else -1 if a*b < 0: -1 else 0
    a_b.append((abs(a), abs(b), sign))

c = Counter(a_b) # ベクトルごとにグループ分け
key_list = list(c.keys())

d = defaultdict(list) # [a, b] あるngなペアのそれぞれの要素の個数
for key in key_list:
    a, b, sign = key
    if d[(b, a, -sign)]: # ダブルカウントしないように
        continue 
    if c[(b, a, -sign)] != 0:
        d[(a, b, sign)] = [c[(a, b, sign)], c[(b, a, -sign)]]

ans = 1 # 積算の単位元
used_cnt = double_zero_cnt # 組めないものがあるイワシの個数
for key in d.keys():
    if d[key] == []: # 前のループで調べると[]が生まれてしまう
        continue
    x, y = d[key]
    used_cnt += (x + y)
    mul = (pow(2, x, mod) + pow(2, y, mod) - 1) % mod # このグループからは、片方ずつからしか出せない。何も選ばないがダブルカウントになる。
    ans *= mul
    ans %= mod

ans *= pow(2, n - (used_cnt), mod) # まだ使われていないイワシは好きな組み合わせ可能
ans += double_zero_cnt # 両方0のものは1つにつき自分のみの1通り
ans -= 1 # 0匹は選べない
ans %= mod
print(ans)







### FIXED CODE ###

import sys
input = sys.stdin.readline
mod = 10**9 + 7
n = int(input())
ab = [[int(x) for x in input().split()] for _ in range(n)]
from collections import defaultdict, Counter
import math
double_zero_cnt = 0
a_zero_cnt = 0
b_zero_cnt = 0
d = defaultdict(list) # [a, b] ngのそれぞれの個数
a_b = []
for a, b in ab:
    if a == 0 and b == 0: 
        double_zero_cnt += 1
        continue
    elif a == 0:
        a_zero_cnt += 1
        continue
    elif b == 0:
        b_zero_cnt += 1
        continue
    g = math.gcd(a, b)
    a //= g
    b //= g
    if b < 0:
        b *= (-1)
        a *= (-1) # 必ずbは正
    a_b.append((a, b))
c = Counter(a_b)
key_list = list(c.keys())
for key in key_list:
    a, b = key
    if a < 0:
        a_ = a*(-1)
        b_ = b*(-1)
    else:
        a_ = a
        b_ = b
    if d[(-b_, a_)] != []:
        continue
    if c[(-b_, a_)] != 0:
        d[(a, b)] = [c[(a, b)], c[(-b_, a_)]]
ans = 1
used_cnt = double_zero_cnt
for key in d.keys():
    if d[key] == []:
        continue
    x, y = d[key]
    used_cnt += (x + y)
    mul = (pow(2, x, mod) + pow(2, y, mod) - 1) % mod
    ans *= mul
    ans %= mod
if a_zero_cnt > 0 and b_zero_cnt > 0:
    ans *= (pow(2, a_zero_cnt, mod) + pow(2, b_zero_cnt, mod) - 1)
    ans %= mod
    used_cnt += a_zero_cnt + b_zero_cnt
elif a_zero_cnt > 0:
    ans *= pow(2, a_zero_cnt, mod)
    ans %= mod
    used_cnt += a_zero_cnt
elif b_zero_cnt > 0:
    ans *= pow(2, b_zero_cnt, mod)
    ans %= mod
    used_cnt += b_zero_cnt
ans *= pow(2, n - (used_cnt), mod)
ans %= mod
ans -= 1
ans += double_zero_cnt
ans %= mod
print(ans)
y = input()
y = input().split()
y = [ int(x) for x in y]
sum_go = []
sum_back = []
for i in range(0, num):
    sum_go.append(sum(y[0:i] ))
    sum_back.append(sum(y[i:] ))
result = []
for i in range(len(sum_go)):
    result.append( abs(sum_go[i] - sum_back[i]) )
print(min(result))

### FIXED CODE ###

y = input()
y = input().split()
y = [ int(x) for x in y]
sum_go = []
sum_back = []
for i in range(1, len(y)):
    sum_go.append(sum(y[0:i] ))
    sum_back.append(sum(y[i:] ))
#print(sum_go)
#print(sum_back)
result = []
for i in range(len(sum_go)):
    result.append( abs(sum_go[i] - sum_back[i]) )
print(min(result))
#include <math.h>
#include <bits/stdc++.h>
#include <map>
#include <set>
#include <iostream>

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)

using namespace std;


int main()
{
    int N, M;
    cin >> N >> M;
    map<int, set<pair<int, int>>> OUT;
    map<int, set<int>> IN;
    set<int> start;
    FOR (i,0,N){
        start.insert(i);
    }
    FOR(i,0,N+M-1){
        int a, b;
        cin >> a >> b;
        start.erase(b - 1);
        OUT[a - 1].insert(make_pair(i, b - 1));
        IN[b - 1].insert(i);
    }
    vector<int> P(N, 0);
    while (start.size()>0){
        int now = *start.begin();
        start.erase(now);
        for (auto x:OUT[now]){
            int b = x.first;
            int nex = x.second;
            IN[nex].erase(b);
            if (IN[nex].size()==0){
                start.insert(nex);
                P[nex] = now + 1;
            }
        }
    }
    FOR(i,0,N){
        cout << P[i] << endl;
    }
}


### FIXED CODE ###

import sys
input=sys.stdin.readline
N,M=map(int,input().split())
from collections import defaultdict
OUT=defaultdict(set)
IN=defaultdict(int)
for i in range(N+M-1):
    a,b=map(int,input().split())
    OUT[a-1]|={b-1}
    IN[b-1]+=1
P=[0]*N
start={i for i in range(N) if IN[i]==0}
while len(start)>0:
    now=start.pop()
    for nex in OUT[now]:
        IN[nex]-=1
        if IN[nex]==0:
            start|={nex}
            P[nex]=now+1
[print(p) for p in P]
import sys
n = int(input())
d = list(map(int, input().split()))
m = {}
ans = 1

if d[0] != 0:
    print(0)
    sys.exit()

for i in range(n):
    num = d[i]
    if num in m:
        m[num] += 1
    else:
        m[num] = 1

#print(m)
#print(max(m))

#for i in range(1, max(m)+1):
for i in range(0, max(m)):
    if i not in m:
        print(0)
        sys.exit()
    prevCnt = m[i]
    curCnt = m[i+1]
    ans *= prevCnt ** curCnt

print(ans % 998244353)







### FIXED CODE ###

import sys
n = int(input())
d = list(map(int, input().split()))
m = {}
ans = 1

if d[0] != 0:
    print(0)
    sys.exit()

if d.count(0) > 1:
    print(0)
    sys.exit()

for i in range(n):
    num = d[i]
    if num in m:
        m[num] += 1
    else:
        m[num] = 1

# if len(m) < n:
#     print(0)
#     sys.exit()

#print(m)
#print(max(m))
maxV = max(m.keys())

#for i in range(1, max(m)+1):
#for i in range(0, max(m)):
for i in range(0, maxV):
    if i not in m or i + 1 not in m:
        print(0)
        sys.exit()
    prevCnt = m[i]
    curCnt = m[i+1]
    # prevCnt = m[i] % 998244353
    #curCnt = m[i+1] % 998244353
    ans *= prevCnt ** curCnt
    #ans *= (prevCnt ** curCnt) % 998244353

print(ans % 998244353)
def lcs_size():
  X = input()
  Y = input()
  
  a = len(X)
  b = len(Y)
  
  c = [[0 for i in range(a)] for j in range(b)]
  for i in range(a):
    for j in range(b):
      if X[i] == Y[j]:
        c[i][j] = c[i-1][j-1] + 1
      else:
        c[i][j] = max(c[i-1][j], c[i][j-1])
      maxl = max(maxl, c[i][j])
  
  return maxl

q = input()

for i in range(q):
  print lcs_siz()

### FIXED CODE ###

def lcs_size():
  X = raw_input()
  Y = raw_input()
  a = len(X)
  b = len(Y)
  z2 = [0 for i in range(b+1)]

  for i in range(a):
    ch = X[i]
    z1 = z2 + []
    for j in range(b):
      if ch == Y[j]:
        z2[j+1] = z1[j] + 1
      elif z2[j+1] < z2[j]:
        z2[j+1] = z2[j]

  return z2[-1]

q = input()
for k in range(q):
  print lcs_size()
s = input()
print(s.replace(',', ' '))
a = input()
print(a.replace(',' , ' ')

### FIXED CODE ###

a,b,c = input().split(",")
print(a, b, c)
a = input()
b= input()
x = a*b

if x%2==0:
    print("Odd")
else:
    print("even")


### FIXED CODE ###

a,b = map(int,input().split())
if (a*b)%2==0:
    print("Even")
else:
    print("Odd")
s=input()
print(count.s("1"))

### FIXED CODE ###

s=input()
print(s.count("1"))
X, A, B = map(int,input().split())
m = B - A
if(m <= 0):
  print("delicious")
elif(X => m):
  print("safe")
else:
  print("dangerous")

### FIXED CODE ###

X, A, B = map(int,input().split())
m = B - A
if(m <= 0):
  print("delicious")
elif(m <= X):
  print("safe")
else:
  print("dangerous")
n,m=[int(i) for i in input().split()]
id=[[int(i) for i in input().split()]+[j] for j in range(m)]

print(id)

pre_num=[0]*(n+1)
ans=[""]*m

id.sort(key=lambda x:x[1])

for p,y,i in id:
    pre_num[p]+=1
    ans[i]=str(p).zfill(6)+str(pre_num[p]).zfill(6)
    
print("\n".join(ans))


### FIXED CODE ###

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

print(t//a * b)
N = input()
A = list(map(int, input().split()))

answer = 1
if 0 in A:
  print(0)
else:
  for i in A:
    answer *= i
    if answer > 10**18:
      answer = -1
      break
  print(answer)
  

### FIXED CODE ###

a = list(map(int, input().split()))
print(a[0] * a[1])
N,K = map(int,input().split())
S = list(input())
happy = 0
L = 0
R = 0
for i in range(N-1):
  if S[i] == S[i+1]:
    happy += 1
  elif S[i] == 'L' and S[i+1] == 'R':
    L += 1
  else:
    R += 1
if min(R,L) >= K:
  happy += K*2
else:
  happy += min(R,L) + K
if happy <= len(S) - 1:
  print(happy)
else:
  print(len(S) - 1)

### FIXED CODE ###

N,K = map(int,input().split())
S = list(input())
happy = 0
L = 0
R = 0
for i in range(N-1):
  if S[i] == S[i+1]:
    happy += 1
  elif S[i] == 'L' and S[i+1] == 'R':
    L += 1
  else:
    R += 1
if min(R,L) >= K:
  happy += K*2
else:
  happy += min(R,L) + K
if happy <= len(S) - 1:
  print(happy)
else:
  print(len(S) - 1)
import numpy as np
if __name__ == "__main__":
    a, b, c, d=(int(x) for x in input().split())
    arr = [a*c, a*d, b*c, b*d]
    print(arr.max())

### FIXED CODE ###

import numpy as np
if __name__ == "__main__":
    a, b, c, d=(int(x) for x in input().split())
    arr = np.array([a*c, a*d, b*c, b*d])
    print(arr.max())
import sys
sys.setrecursionlimit(100000)
n=int(input())
t=[int(i) for i in sys.stdin]
def gcd(x,y):
  if y==0:
    return x
  return gcd(y,x%y)
x=t[0]
for i in range(1,n):
  y=x*t[i]//gcd(x,t[i])
  x=y
print(y)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
n=int(input())
t=[int(i) for i in sys.stdin]
if n==1:
  print(t[0])
  exit()
def gcd(x,y):
  if y==0:
    return x
  return gcd(y,x%y)
x=t[0]
for i in range(1,n):
  y=x*t[i]//gcd(x,t[i])
  x=y
print(y)
n = int(input())
mod = 10**9+7
count = [0]*(n+1)
l = [0]+[int(input()) for i in range(n)]
dp = [0]*(n+1)
dp[0] = 1
for i in range(1,n+1):
    if l[i] == l[i-1]:
        dp[i] = dp[i-1]
        continue
    dp[i] = (dp[i-1]+count[l[i]])%mod
    count[l[i]] = dp[i]
print(dp[-1])

### FIXED CODE ###

n = int(input())
mod = 10**9+7
count = [0]*(2*10**5+1)
l = [0]+[int(input()) for i in range(n)]
dp = [0]*(n+1)
dp[0] = 1
for i in range(1,n+1):
    if l[i] == l[i-1]:
        dp[i] = dp[i-1]
        continue
    dp[i] = (dp[i-1]+count[l[i]])%mod
    count[l[i]] = dp[i]
print(dp[-1])
N = int(input())
D = list(map(int, input().split()))
n = N // 2
_n = n - 1
n_ = n + 1
D.sort()
cnt = 0
for i in range(max(D)) :
  if(D[_n] < i and i < D[n_]) :
    if(D[_n] != D[n_]) :
      cnt += 1
    else :
      pass
  else :
    pass
print(cnt)

### FIXED CODE ###

N = int(input())
D = list(map(int, input().split()))
D.sort()
ans = 0
for i in range(N // 2) :
  cnt = len(list(filter(lambda x : x <= D[N // 2 - 1 + i], D)))
  if(cnt == N // 2) :
    ans += D[N // 2] - D[N // 2 - 1]
  elif(cnt > N // 2) :
    break
  else :
    pass
print(ans)