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

# 久々の幅優先探索……

n, k = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(n-1)]

def add_edge(u, v ):
	G[u].append(v)
	G[v].append(u)

G = [[] for _ in range(n)] #グラフの隣接リスト表現
for edge in edges:
	add_edge(edge[0]-1, edge[1]-1)

n_colors = [-1] * n
n_colors[0] = k
queue = [0]

count = 0
for v in G[0]:
	queue.append(v)
	n_colors[v] = k - count - 1 #※
	count += 1

while(len(queue) > 0):
	now = queue[0]

	del queue[0]

	count = 0
	for v in G[now]:
		if n_colors[v] >= 0:
			pass
		else:
			queue.append(v)
			n_colors[v] = k - count - 2
			count += 1

			if n_colors[v] == 0:
				print(0)
				exit()

ans = 1
for i in range(n):
	ans *= n_colors[i]
	ans %= (10 ** 9 + 7)

print(ans)


### FIXED CODE ###

# 久々の幅優先探索……

import queue

n, k = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(n-1)]

def add_edge(u, v ):
	G[u].append(v)
	G[v].append(u)

G = [[] for _ in range(n)] #グラフの隣接リスト表現
for edge in edges:
	add_edge(edge[0]-1, edge[1]-1)

q = queue.Queue()
q.put(0)

n_colors = [-1] * n
n_colors[0] = k

count = 0
for v in G[0]:
	q.put(v)
	n_colors[v] = k - count - 1 #※
	count += 1

while(q.qsize() > 0):
	now = q.get()
	count = 0
	for v in G[now]:
		if n_colors[v] >= 0:
			pass
		else:
			q.put(v)
			n_colors[v] = k - count - 2
			count += 1

			if n_colors[v] == 0:
				print(0)
				exit()

ans = 1
for i in range(n):
	ans *= n_colors[i]
	ans %= (10 ** 9 + 7)

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

x=input()
while "SSSSSTTTTT" in x:x=x.replace("SSSSSTTTTT","")
while "ST" in x:x=x.replace("ST","")
print(len(x))

### FIXED CODE ###

l=[]
for i in input():
    if i=="S":l.append("S")
    elif len(l)==0 or l[-1]=="T":l.append("T")
    else:l.pop()
print(len(l))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
import math
eps = 1e-12

def calc_intersection_points(circle0, circle1):
    x0, y0, r0 = circle0
    x1, y1, r1 = circle1
    d = math.hypot(x0 - x1, y0 - y1)
    if d > r0 + r1 or d < abs(r0 - r1):
        return []
    ret = []
    if r0 + r1 == d:
        a = r0
        h = 0.0
    else:
        a = (r0**2 - r1**2 + d**2) / (2.0 * d)
        h = math.sqrt(r0**2 - a**2)
    x2 = x0 + a * (x1 - x0) / d
    y2 = y0 + a * (y1 - y0) / d
    x3 = x2 + h * (y1 - y0) / d
    y3 = y2 - h * (x1 - x0) / d
    ret.append((x3, y3))
    if h == 0:
        return ret
    x4 = x2 - h * (y1 - y0) / d
    y4 = y2 + h * (x1 - x0) / d
    ret.append((x4, y4))
    return ret


n, k = map(int, input().split())
niku = []
for _ in range(n):
    x, y, c = map(int, input().split())
    niku.append((x, y, c))

l = 0.0; r = 10**8
for _ in range(1000):
    mid = (l + r) / 2.0
    circles = []
    for x, y, c in niku:
        circles.append((x, y, mid / c))
    points = []
    for i in range(n):
        for j in range(i+1, n):
            points += calc_intersection_points(circles[i], circles[j])
    for x, y, _ in niku:
        points.append((x, y))
    cooked = 0
    for x, y in points:
        ret = 0
        for cx, cy, cr in circles:
            if math.hypot(x - cx, y - cy) <= cr + eps:
                ret += 1
        if ret > cooked:
            cooked = ret
    if cooked >= k:
        r = mid
    else:
        l = mid
print(l)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
import math
eps = 1e-12

def calc_intersection_points(circle0, circle1):
    x0, y0, r0 = circle0
    x1, y1, r1 = circle1
    d = math.hypot(x0 - x1, y0 - y1)
    if d > r0 + r1 or d < abs(r0 - r1):
        return []
    ret = []
    if r0 + r1 == d:
        a = r0
        h = 0.0
    else:
        a = (r0**2 - r1**2 + d**2) / (2.0 * d)
        h = math.sqrt(r0**2 - a**2)
    x2 = x0 + a * (x1 - x0) / d
    y2 = y0 + a * (y1 - y0) / d
    x3 = x2 + h * (y1 - y0) / d
    y3 = y2 - h * (x1 - x0) / d
    ret.append((x3, y3))
    if h == 0:
        return ret
    x4 = x2 - h * (y1 - y0) / d
    y4 = y2 + h * (x1 - x0) / d
    ret.append((x4, y4))
    return ret


n, k = map(int, input().split())
niku = []
for _ in range(n):
    x, y, c = map(int, input().split())
    niku.append((x, y, c))

l = 0.0; r = 10**8
for _ in range(64):
    mid = (l + r) / 2.0
    circles = []
    for x, y, c in niku:
        circles.append((x, y, mid / c))
    points = []
    for i in range(n):
        for j in range(i+1, n):
            points += calc_intersection_points(circles[i], circles[j])
    for x, y, _ in niku:
        points.append((x, y))
    cooked = 0
    for x, y in points:
        ret = 0
        for cx, cy, cr in circles:
            if math.hypot(x - cx, y - cy) <= cr + eps:
                ret += 1
        if ret > cooked:
            cooked = ret
    if cooked >= k:
        r = mid
    else:
        l = mid
print(l)
### BUGGY CODE ###

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

A = list(map(int, input().split()))
AA = []
for i in range(2):
    AA.extend(A)

x = 0
for i in range(len(A)):
    for j in range(len(A)-1, i, -1):
        if A[j] < A[j-1]:
            A[j], A[j-1] = A[j-1], A[j]
            x += 1
M = 10**9 + 7

y = 0

for i in range(len(AA)):
    for j in range(len(AA)-1, i, -1):
        if AA[j] < AA[j-1]:
            AA[j], AA[j-1] = AA[j-1], AA[j]
            y += 1

a = (K*x) % M
b = int(y - 2*x) * int( (K*(K-1)//2) % M)
ans = ((a+b)  % M)
print(int(ans))

### FIXED CODE ###

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

A = list(map(int, input().split()))
AA = []
for i in range(2):
    AA.extend(A)

x = 0
for i in range(N):
    for j in range(i+1, N):
        if A[j] < A[i]:
            x += 1
M = 10**9 + 7

y = 0
NN = N*2
for i in range(NN):
    for j in range(i+1, NN):
        if AA[j] < AA[i]:
            y += 1

a = (K*x)
b = (y - 2*x) * (K*(K-1)//2)
ans = ((a+b)  % M)
print(int(ans))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

def main():
    n, q = map(int, input().split())
    # バラバラに持ちたいなら
    # for i in range(n-1):
    #     a, b = map(int, input().split())
    # for i in range(q):
    #     q, x = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(n-1)]
    px = [list(map(int, input().split())) for i in range(q)]
    # print(ab)
    # print(qx)
    # indexがノード
    adj = [[] for _ in range(n+1)]
    for a, b in ab:
            adj[a].append(b)
            adj[b].append(a)
    # print(adj)
    # indexが直接初めにノードに加えられる得点
    v = [0] * (n+1)
    for p,x in px:
        v[p] += x

    def dfs(cur, parent):
        for chl in adj[cur]:
            if chl == parent: 
                continue
            v[chl] += v[cur] 
            dfs(chl, cur)

    dfs(1, 0)
    ans = ' '.join(map(str,v[1:]))
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import deque
# sys.setrecursionlimit(10**7)

def main():
    n, q = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(n-1)]
    px = [list(map(int, input().split())) for i in range(q)]
    adj = [[] for _ in range(n+1)]
    for a, b in ab:
            adj[a].append(b)
            adj[b].append(a)
    # indexが直接初めにノードに加えられる得点
    v = [0] * (n+1)
    for p,x in px:
        v[p] += x
    # 子をindexで、親ノードを要素で
    parent = [None] * (n+1)
    q = deque([1])
    while q:
        par = q.pop()
        for chl in adj[par]:
            if chl == parent[par]:
                continue
            v[chl] += v[par]
            parent[chl] = par
            q.append(chl)
    ans = ' '.join(map(str,v[1:]))
    print(ans)
    
    # def dfs(cur, parent):
    #     for chl in adj[cur]:
    #         print('p', parent)
    #         if chl == parent: 
    #             continue
    #         v[chl] += v[cur]
    #         print('chl,cur', chl, cur)
    #         dfs(chl, cur)

    # dfs(1, 1)
    # ans = ' '.join(map(str,v[1:]))
    # print(ans)

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

n, k = map(int, input().split())
a_list = list(map(int, input().split()))
a_list.sort()

import math


def cmb(n, r):
    o = math.factorial(n)
    u = math.factorial(r) * math.factorial(n - r)
    return o // u


max_val = 0
min_val = 0
val = int(cmb(n - 1, k - 1))
for i in range(n - k + 1):
    if i != 0:
        val = int(val * (n - i - k + 1) // (n - i))
    max_val = int(max_val + (((a_list[-(i + 1)]) * val))) % (10 ** 9 + 7)
    min_val = int(min_val + ((a_list[i]) * val)) % (10 ** 9 + 7)

print(int((max_val - min_val) % (10 ** 9 + 7)))

### FIXED CODE ###

n, k = map(int, input().split())
a_list = list(map(int, input().split()))
a_list.sort()


mod = 10 ** 9 + 7
f_list = [1]
for i in range(1,n+1):
    f_list.append((f_list[-1] * i) % mod)
def comb(n,r):
    return f_list[n] * (pow(f_list[r], mod-2, mod) * pow(f_list[n-r], mod-2, mod) % mod) % mod


max_val = 0
min_val = 0
for i in range(n - k + 1):
    val = comb(n - i - 1, k - 1)
    max_val = (max_val + (((a_list[-(i + 1)]) * val))) % (10 ** 9 + 7)
    min_val = (min_val + ((a_list[i]) * val)) % (10 ** 9 + 7)

print(int((max_val - min_val) % (10 ** 9 + 7)))
### BUGGY CODE ###

r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
n_max=2*(10**6+1)
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
  FI[i+1]=pow(F[i+1],mod-2,mod)
def comb(x,y):
  return (F[x]*FI[x-y]*FI[y])%mod

def f(x,y):
  return comb(x+y+2,y+1)-1

print((f(r2,c2)-f(r2,c1-1)-f(r1-1,c2)+f(r1-1,c1-1))%mod)


### FIXED CODE ###

r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
n_max=2*(10**6+1)
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
  FI[i+1]=pow(F[i+1],mod-2,mod)
def comb(x,y):
  return (F[x]*FI[x-y]*FI[y])%mod

def f(x,y):
  return comb(x+y+2,y+1)-1

print((f(r2,c2)-f(r2,c1-1)-f(r1-1,c2)+f(r1-1,c1-1))%mod)
### BUGGY CODE ###

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

P=tuple(map(int,input().split()))

Group=[i for i in range(N+1)]


Swap=[None]*M
for i in range(M):
    Swap[i]=list(map(int,input().split()))

judge=1
while judge==1:
    judge=0
    for i in range(M):
        if (Group[Swap[i][1]],Group[Swap[i][0]])!=(min(Group[Swap[i][0]], Group[Swap[i][1]]),min(Group[Swap[i][0]], Group[Swap[i][1]])):
            Group[Swap[i][1]],Group[Swap[i][0]]=min(Group[Swap[i][0]], Group[Swap[i][1]]),min(Group[Swap[i][0]], Group[Swap[i][1]])
            judge=1

count=0

for i in range(N):
    if Group[P[i]]==Group[i+1]:
        count+=1


print(count)
        


### FIXED CODE ###

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

Group=[i for i in range(N+1)]


Swap=[None]*M
for i in range(M):
    Swap[i]=sorted(map(int,input().split()))

def find(x):
    while Group[x] != x:
        x=Group[x]
    return x

for i in range(M):
    if find(Swap[i][1]) != find(Swap[i][0]):
        Group[find(Swap[i][1])]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[find(Swap[i][0])]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[Swap[i][1]]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[Swap[i][1]]=min(find(Swap[i][1]),find(Swap[i][0]))

count=0

for i in range(N):
    if find(P[i])==find(i+1):
        count+=1


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

import sys

N = int(input())
ana = {}
answer = 0

for i in range(N):
    s = sorted(input())
    new_str = ''.join(s)
    flag = 0

    for k in (ana.keys()):
        if new_str == k:
            ana[k] += 1
            answer += ana[k]
            flag = 1

    if flag == 0:
        ana[new_str] = 0

print(answer)

### FIXED CODE ###

N = int(input())
ana = {}
answer = 0

for i in range(N):
    s = sorted(input())
    new_str = ''.join(s)
    flag = 0

    if new_str in ana.keys():
        ana[new_str] += 1
        answer += ana[new_str]
        flag = 1

    if flag == 0:
        ana[new_str] = 0

print(answer)
### BUGGY CODE ###

import collections

def prime_factorize(n):
    prime_factor_list = []
    while n%2 == 0:
        prime_factor_list.append(2)
        n //= 2
    f = 3
    while f*f <= n:
        if n%f == 0:
            prime_factor_list.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        prime_factor_list.append(n)
    
    prime_factor = collections.Counter(prime_factor_list)

    return prime_factor

def yakusuu(n):
    c = prime_factorize(n)
    res = 1
    for i in c.values():
        res *= (i + 1)
    
    return res

n = int(input())

ans = 0

for i in range(1, n+1):
    y = yakusuu(i)
    ans += i * y

print(ans)


### FIXED CODE ###

n = int(input())

def s(n):
    return n * (n + 1) // 2

ans = 0

for i in range(1, n+1):
    tmp = n // i
    ans += i * s(tmp)

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

import numpy as np
import sys
input = sys.stdin.readline


def main():
    H, W = map(int, input().split())
    s = [list(input()) for _ in range(H)]
    s = np.array(s)
    L = np.zeros((H, W))
    R = np.zeros((H, W))
    T = np.zeros((H, W))
    B = np.zeros((H, W))
    for h in range(H):
        for w in range(W):
            if s[h, w] == "#":
                R[h, w] = 0
            elif w == 0:
                R[h, w] = 1
            else:
                R[h, w] = R[h, w - 1] + 1
    for h in range(H):
        for w in reversed(range(W)):
            if s[h, w] == "#":
                L[h, w] = 0
            elif w == W - 1:
                L[h, w] = 1
            else:
                L[h, w] = L[h, w + 1] + 1
    for w in range(W):
        for h in range(H):
            if s[h, w] == "#":
                B[h, w] = 0
            elif h == 0:
                B[h, w] = 1
            else:
                B[h, w] = B[h-1, w] + 1
    for w in range(W):
        for h in reversed(range(H)):
            if s[h, w] == "#":
                T[h, w] = 0
            elif h == H - 1:
                T[h, w] = 1
            else:
                T[h, w] = T[h + 1, w] + 1
    ans = 0
    for h in range(H):
        for w in range(W):
            res = R[h, w] + L[h, w] + B[h, w] + T[h, w] - 3
            ans = max(ans, res)
    print(int(ans))


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    H, W = map(int, input().split())
    s = [list(input()) for _ in range(H)]
    L = [[0] * W for _ in range(H)]
    R = [[0] * W for _ in range(H)]
    T = [[0] * W for _ in range(H)]
    B = [[0] * W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if s[h][w] == "#":
                R[h][w] = 0
            elif w == 0:
                R[h][w] = 1
            else:
                R[h][w] = R[h][w - 1] + 1
    for h in range(H):
        for w in reversed(range(W)):
            if s[h][w] == "#":
                L[h][w] = 0
            elif w == W - 1:
                L[h][w] = 1
            else:
                L[h][w] = L[h][w + 1] + 1
    for w in range(W):
        for h in range(H):
            if s[h][w] == "#":
                B[h][w] = 0
            elif h == 0:
                B[h][w] = 1
            else:
                B[h][w] = B[h-1][w] + 1
    for w in range(W):
        for h in reversed(range(H)):
            if s[h][w] == "#":
                T[h][w] = 0
            elif h == H - 1:
                T[h][w] = 1
            else:
                T[h][w] = T[h + 1][w] + 1
    ans = 0
    for h in range(H):
        for w in range(W):
            res = R[h][w] + L[h][w] + B[h][w] + T[h][w] - 3
            ans = max(ans, res)
    print(int(ans))


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

n = int(input())
a = list(map(int, input().split()))
sum = 0
for i in range(0,n-1):
    for j in range(i+1,n):
        b = a[i]*a[j]
        sum = sum + b
print(sum%(10**9+7))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
A = sum(a)
s = 0
for i in range(n-1):
    A = A - a[i]
    b = (a[i]*A)%(10**9+7)
    s = s + b
print(s%(10**9+7))
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,z,w = LI()
    a = LI()
    m = {}
    def f(z,w,i,t):
        if i >= n:
            return abs(z-w)
        if t:
            k = (-1,w,i)
            if k in m:
                return m[k]
            r = -1
            for j in range(i,n):
                jr = f(a[j],w,j+1,False)
                if r < jr:
                    r = jr
            m[k] = r
        else:
            k = (z,-1,i)
            if k in m:
                return m[k]
            r = inf
            for j in range(i,n):
                jr = f(z,a[j],j+1,True)
                if r > jr:
                    r = jr
            m[k] = r
        return m[k]

    return f(z,w,-1,True)



print(main())




### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,z,w = LI()
    a = LI()
    m = {}
    def f(z,w,i,t):
        if i >= n:
            return abs(z-w)
        if t:
            k = (-1,w,i)
            if k in m:
                return m[k]
            r = -1
            for j in range(i,n):
                jr = f(a[j],w,j+1,False)
                if r < jr:
                    r = jr
            m[k] = r
        else:
            k = (z,-1,i)
            if k in m:
                return m[k]
            r = inf
            for j in range(i,n):
                jr = f(z,a[j],j+1,True)
                if r > jr:
                    r = jr
            m[k] = r
        return m[k]

    return f(z,w,-1,True)



print(main())
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from operator import itemgetter

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

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

    def root(self, x):
        if self.par[x]<0:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]

    def unite(self,x,y):
        x = self.root(x)
        y = self.root(y)
        if x==y:
            return

        if self.par[x]>self.par[y]:
            x,y = y,x

        self.par[x] += self.par[y]
        self.par[y] = x

    def size(self,x):
        return -self.par[self.root(x)]

def kruskal(e,n):
    l = []
    for v in range(n):
        for u,c in e[v]:
            l.append((c,v,u))
    l.sort()

    uf = UnionFind(n)
    cost = 0
    res = []
    for c,v,u in l:
        if uf.same(v,u):
            continue
        res.append((v,u,c))
        cost += c
        uf.unite(v,u)
    return res,cost


n = int(input())
e = [[] for _ in range(n)]

ixy = []
for i in range(n):
    x,y = map(int, input().split())
    ixy.append((i,x,y))

ixy.sort(key=itemgetter(1,2))
for i in range(n-1):
    v,a,b = ixy[i]
    u,c,d = ixy[i+1]
    e[v].append((u,min(abs(a-c),abs(b-d))))
    e[u].append((v,min(abs(a-c),abs(b-d))))

ixy.sort(key=itemgetter(2,1))
for i in range(n-1):
    v,a,b = ixy[i]
    u,c,d = ixy[i+1]
    e[v].append((u,min(abs(a-c),abs(b-d))))
    e[u].append((v,min(abs(a-c),abs(b-d))))

r,cost = kruskal(e,n)
print(cost)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from operator import itemgetter

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

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

    def root(self, x):
        if self.par[x]<0:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]

    def unite(self,x,y):
        x = self.root(x)
        y = self.root(y)
        if x==y:
            return

        if self.par[x]>self.par[y]:
            x,y = y,x

        self.par[x] += self.par[y]
        self.par[y] = x

    def size(self,x):
        return -self.par[self.root(x)]

def kruskal(e,n):
    l = []
    for v in range(n):
        for u,c in e[v]:
            l.append((c,v,u))
    l.sort()

    uf = UnionFind(n)
    cost = 0
    res = []
    for c,v,u in l:
        if uf.same(v,u):
            continue
        res.append((v,u,c))
        cost += c
        uf.unite(v,u)
    return res,cost


n = int(input())
e = [[] for _ in range(n)]

ixy = []
for i in range(n):
    x,y = map(int, input().split())
    ixy.append((i,x,y))

ixy.sort(key=itemgetter(1,2))
for i in range(n-1):
    v,a,b = ixy[i]
    u,c,d = ixy[i+1]
    e[v].append((u,min(abs(a-c),abs(b-d))))

ixy.sort(key=itemgetter(2,1))
for i in range(n-1):
    v,a,b = ixy[i]
    u,c,d = ixy[i+1]
    e[v].append((u,min(abs(a-c),abs(b-d))))

r,cost = kruskal(e,n)
print(cost)
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
mod = pow(10,9)+7
s = 0
for i in range(N-1):
    b = a[i]
    for j in range(i+1,N):
        s += b*a[j]
        s %= mod
print(s)

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
a_s = sum(a)
mod = 10**9+7
s = 0
for i in range(N-1):
    b = a[i]
    a_s -= b
    s += b*(a_s)
    s %= mod
print(s)
### BUGGY CODE ###


S = input()
T = input()
N = len(S)
M = len(T)

dp = [ [0]* (len(T)+1) for _ in range(len(S)+1)]

for i in range(1, len(S)+1):
    for j in range(1,len(T)+1):
        if S[i-1] == T[j-1]:
            dp[i][j] = max(dp[i][j] , dp[i-1][j-1] + 1)
        else:
            dp[i][j] = max(dp[i][j] , dp[i-1][j], dp[i][j-1], dp[i-1][j-1] )
res = []

i = N
j = M
cnt = dp[N][M]

while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        i -= 1 ; j -= 1
        res.append(S[i])
# while cnt :
#     while cnt == dp[i][j]:
#         i -= 1
#     i += 1
#     while cnt == dp[i][j]:
#         j -= 1
#     j += 1
#     res.append(S[i-1])
#     cnt -= 1
#     i -= 1; j -= 1
print("".join(reversed(res)))
    


### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
# FROM : https://atcoder.jp/contests/dp/submissions/4011183

S,T = input(), input()
S,T = list(map(lambda x: ord(x)-97, S)), list(map(lambda x: ord(x)-97, T))

# print(S,T)

dp = [ [0] * (len(T)+1)] + [[0]+[None]*len(T) for _ in range(len(S))]

for i,s in enumerate(S):
    for j,t in enumerate(T):
        dp[i+1][j+1] = max(
                dp[i][j+1], 
                dp[i+1][j],
                dp[i][j] + (s==t)
                )
res = []

x,y = len(S), len(T)

while x > 0 and y > 0:
    if dp[x][y] == dp[x-1][y]:
        x -= 1
    elif dp[x][y] == dp[x][y-1]:
        y -= 1
    else:
        x -= 1
        y -= 1
        res.append(chr(S[x]+97))
print(''.join(reversed(res)))
### BUGGY CODE ###

def lcs(x, y):
    a = len(x)
    b = len(y)
    c1 = [0] * (b + 1)
    for i in range(a):
        c2 = c1[:]
        for j in range(b):
            if x[i] == y[j]:
                c1[j+1] = c2[j] + 1
            elif c1[j+1] < c1[j]:
                c1[j+1] = c1[j]
    return c1[-1]
   
n = int(input().rstrip())
ret = [0] * n
for i in range(n):
    s1 = input().rstrip()
    s2 = input().rstrip()
    ret[i] = lcs(s1, s2)
for i in range(n):
    print(ret[i])

### FIXED CODE ###

def lcs(x, y):
    a = len(x)
    b = len(y)
    c1 = [0] * (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 = int(input().rstrip())
ret = []
for i in range(n):
    s1 = input().rstrip()
    s2 = input().rstrip()
    ret.append(lcs(s1, s2))
print(*ret, sep="\n")