Harryxun/stf_run huggingface dataset:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

PRIME = 10 ** 9 + 7
N, M = list(map(int, input().split()))
broken_stairs = []
for _ in range(M):
    broken_stairs.append(int(input()))

prev_broken = -1
cannot = False
ans = 1
for a in broken_stairs:
    if a - prev_broken == 1:
        cannot = True
        break
    ans *= fib(a - prev_broken - 2)
    ans %= PRIME
    prev_broken = a

ans *= fib(N - prev_broken - 1)
ans %= PRIME

if cannot:
    print(0)
else:
    print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def fib_memo(n):
    if n <= 1:
        return 1
    memo = [0] * n
    memo[0] = 1
    memo[1] = 2
    for i in range(2, n):
        memo[i] = (memo[i - 1] + memo[i - 2]) % PRIME
    return memo[n-1]

PRIME = 10 ** 9 + 7
N, M = list(map(int, input().split()))
broken_stairs = []
for _ in range(M):
    broken_stairs.append(int(input()))

prev_broken = -1
cannot = False
ans = 1
for a in broken_stairs:
    if a - prev_broken == 1:
        cannot = True
        break
    ans *= fib_memo(a - prev_broken - 2)
    ans %= PRIME
    prev_broken = a

ans *= fib_memo(N - prev_broken - 1)
ans %= PRIME

if cannot:
    print(0)
else:
    print(ans)
while True:
    h,n = map(int, input().split())
    ls = list(map(int, input().split()))
    if sum(ls) >= h:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

h,n = map(int, input().split())
ls = list(map(int, input().split()))
if sum(ls) >= h:
    print("Yes")
else:
    print("No")
n = int(input())
a = list(map(int, input().split()))
count = 0
L = len(a)
for el in a:
    count += a.count(el)-1
count //= 2
for el in a:
    print(count - a.count(el)+1)

### FIXED CODE ###

n, m = map(int, input().split())
result = (n+m)*(n+m-1)//2 - n*m
print(result)
def down_score(d, c, last_d, score):
    sum = 0
    for i in range(26):
        sum += c[i]*(d-last_d[i])
        
    return (score - sum)


def main():
    D = int(input())

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

    s = [list(map(int, input().split())) for i in range(D)]

    sche = []
    for i in range(D):
        x = int(input())
        sche.append(x)
    
    last_d = [0 for i in range(26)]
    score = 0
    
    for i in range(D):
        score += s[i][sche[i]]
        last_d[sche[i]] = i+1
        score = down_score(i+1, c, last_d, score)
        print(score)
        
if __name__ == "__main__":
    main()


### FIXED CODE ###

import random

def down_score(d, c, last_d, score):
    sum = 0
    for i in range(26):
        sum = sum + c[i]*(d-last_d[i])
        
    return int(score - sum)


def main():
    D = int(input())

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

    s = [list(map(int, input().split())) for i in range(D)]

    sche = []
    for i in range(D):
        x = int(input())
        sche.append(x)
    
    last_d = [0 for i in range(26)]
    score = 0
    
    for i in range(D):
        score += s[i][sche[i]-1]
        last_d[sche[i]-1] = i+1
        score = down_score(i+1, c, last_d, score)
        print(score)
        
if __name__ == "__main__":
    main()
n,l = map(int,input().split())
s = []

for i in range(n):
    s.append(input())

s.sort()

print("".join(s))

### FIXED CODE ###

import math

if sorted(input().split())==['5','5','7']:
    print('YES')
else:
    print('NO')
def Input():
    return mapt(int, input().split(" "))


def main():
    a, b = Input()
    if a % 2 !=  b % 2:
        print("IMPOSSIBLE")
    else:
        print((a+b)//2)

main()

### FIXED CODE ###

def mapt(fn, *args):
    return tuple(map(fn, *args))


def Input():
    return mapt(int, input().split(" "))


def main():
    a, b = Input()
    if a % 2 !=  b % 2:
        print("IMPOSSIBLE")
    else:
        print((a+b)//2)

main()
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

N = int(input())
A = list(map(int, input().split()))
import collections

cA = collections.Counter(A)
new_A = []
for a in A:
    if cA[a] == 1:
        new_A.append(a)
A = new_A

A.sort()
# print(A)

answers = set(A)
for i in range(N):
    dame = set()
    for a in answers:
        if a == A[i]:
            continue
        if a % A[i] == 0:
            dame.add(a)
    answers = answers - dame
ans = len(answers)
print(ans)

### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

import collections
N = int(input())
A = list(map(int, input().split()))
cA = collections.Counter(A)

LIM = 10 ** 6 + 1
# LIM = 25

A.sort()
dp = [1] * LIM

for i in set(A):
    s = i * 2
    while s < LIM:
        dp[s] = 0
        s += i

ans = 0
# print(dp)
for a in A:
    # print("{} {}".format(dp[a], cA[a]))
    if dp[a] and cA[a] == 1:
        # print(a)
        ans += 1
print(ans)
h,n=map(int,input().split())
hp=h
a=[]
b=[]
INF=10**9
dp=[INF for i in range(h+1)]

for i in range(n):
  p,q=map(int,input().split())
  a.append(p)
  b.append(q)

for i in range(n):
  dp[a[i]]=b[i]
  #print(dp)
for i in range(1,h+1):
  if dp[i]==INF:
    #dp[i]=min(dp[i],dp[i-1])
    #print(dp)
    continue
  for j in range(n):
    if i+a[j]<=h:
      dp[i+a[j]]=min(dp[i+a[j]],dp[i]+b[j])
      #print(dp)
    else:
      dp[h]=min(dp[h],dp[i]+b[j])
      #print(dp)
  #dp[i]=min(dp[i],dp[i-1])
  #print(dp)
print(dp[h])
    

### FIXED CODE ###

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

a=[]
b=[]
INF=10**9
dp=[INF for i in range(h+10**4)]

for i in range(n):
  p,q=map(int,input().split())
  a.append(p)
  b.append(q)

dp[0]=0
for i in range(h):
  if dp[i]==INF:
    continue
  for j in range(n):
    if dp[i+a[j]]>=dp[i]+b[j]:
      dp[i+a[j]]=dp[i]+b[j]
print(min(dp[h:]))
import numpy as np
 
n, m, c = map(int, input().split())
 
mp = np.zeros((w, h))
b = list(map(int, input().split()))
num = 0
 
for i in range(n):
  A = list(map(int, input().split()))
  npb = np.array(b)
  npA = np.array(A)
  if np.dot(npA.T, npb) + c > 0:
    num += 1
    
print(num)

### FIXED CODE ###

import numpy as np
 
n, m, c = map(int, input().split())
 
b = list(map(int, input().split()))
num = 0
 
for i in range(n):
  A = list(map(int, input().split()))
  npb = np.array(b)
  npA = np.array(A)
  if np.dot(npA.T, npb) + c > 0:
    num += 1
    
print(num)
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin


def main():
    num_mat = int(stdin.readline())
    data = [int(s) for s in stdin.readline().split()]
    for _ in range(num_mat-1):
        _, row = (int(s) for s in stdin.readline().split())
        data.append(row)
    num_dat = len(data)

    bin_op = tuple(data[i]*data[i+1]*data[i+2] for i in range(num_dat-2))
    parts = [(data[0]*data[1], data[-2]*data[-1]), bin_op]

    for j in range(3, num_mat):
        part = parts[-1]
        new_part = []
        for i in range(num_dat-j):
            a = data[i]
            b = data[i+1]
            c = data[i+j-1]
            d = data[i+j]
            new_part.append(min(part[i] + a*c*d, part[i+1] + a*b*d))
        parts.append(new_part)

    L = data
    print(min(parts[i][0] + parts[-(i+1)][-1] +
              L[0]*L[i+1]*L[-1] for i in range(len(parts))))


main()

### FIXED CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin


def main():
    num_mat = int(stdin.readline())
    r = [int(s) for s in stdin.readline().split()]
    for _ in range(num_mat-1):
        _, row = (int(s) for s in stdin.readline().split())
        r.append(row)

    if num_mat < 2:
        print(0)
        return
    elif num_mat < 3:
        print(r[0]*r[1]*r[2])
        return

    M = []
    M.append([0] * num_mat)
    M.append([r[i]*r[i+1]*r[i+2] for i in range(len(M[-1])-1)])

    for i in range(2, num_mat):
        N = []
        for j in range(num_mat-i):
            N.append(min(M[k][j]+M[i-1-k][1+j+k]+r[j]*r[1+j+k]*r[i+1+j]
                         for k in range(i)))
        M.append(N)
    print(M[-1][0])


main()
from bisect import bisect

N = int(input())
a = list(map(int,input().split()))
g = [[] for _ in range(N)]
for i in range(N-1):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

ans = [0]*N
def dfs(t,f,l,seq):
    l = l.copy()
    seq = seq.copy()
    l.append(a[t])
    print(l,seq)
    i = bisect(seq,l[-1])
    if len(seq)==i:
        seq.append(l[-1])
    else:
        seq[i]=l[-1]
    ans[t] = len(seq)
    for v in g[t]:
        if v != f:
            dfs(v,t,l,seq)
dfs(0,0,[],[])
for i in range(N):
    print(ans[i])


### FIXED CODE ###

from bisect import bisect_left as bisect
import sys
sys.setrecursionlimit(10**9)

N = int(input())
a = list(map(int,input().split()))
g = [[] for _ in range(N)]
for i in range(N-1):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

ans = [0]*N
def dfs(t,f,l):
    res = 0
    i = bisect(l,a[t])
    if len(l)==i:
        l.append(a[t])
    else:
        res = [i,l[i]]
        l[i]=a[t]
    ans[t] = len(l)
    for v in g[t]:
        if v != f:
            back = dfs(v,t,l)
            if back:
                l[back[0]] = back[1]
            else:
                l.pop()
    return res
dfs(0,0,[])
for i in range(N):
    print(ans[i])
S=input()
D=[SUN,MON,TUE,WED,THU,FRI,SAT]
Today=D.index(S)
print(7-Today)

### FIXED CODE ###

S=input()
D=['SUN','MON','TUE','WED','THU','FRI','SAT']
Today=D.index(S)
print(7-Today)
import numpy as np
N,K=map(int, input().split())
A =list(map(int,input().split()))
MOD = 10 ** 9 + 7
if N==K:
  ans0 = 1
  for a in A[0:N]:
    ans0 *= a
    ans0 %= MOD
  print(ans0)
  exit()
A=sorted(A)  
if (K%2==1 and A[-1]<0):
  ans1 = 1
  for a in A[N-K:N]:
    ans1 *= a
    ans1 %= MOD
  print(ans1)
  exit()

A=sorted(A, key=lambda x:abs(x), reverse=True)
AA=[np.sign(i) for i in A]

ansA = 1
for a in A[0:K]:
  ansA *= a
  ansA %= MOD
ansAA = AA[0:K].count(-1)%2
if ansA==0 or ansAA==0:
  print(ansA)
  exit()

while ansA>0:
  ansA-=MOD

B1=A[0:K]
B2=sorted(A[K:N])
Bp=[i for i in A[0:K] if i>0]
Bm=[i for i in A[0:K] if i<0]

if B2[0]>0:B2.insert(0,0)
if B2[-1]<0:B2.insert(-1,0)
if not Bp:Bp.insert(0,B1[-1])
if not Bm:Bm.insert(0,B1[0])
  
#print(Bp,Bm,B2)

B1.remove(Bp[-1])
B1.append(min(B2[0],0))
#print(B1)
ansB = 1
for a in B1[0:K]:
  ansB *= a
  ansB %= MOD

C1=A[0:K]
C1.remove(Bm[-1])
C1.append(max(B2[-1],0))

ansC = 1
for a in C1[0:K]:
  ansC *= a
  ansC %= MOD

if abs(Bp[-1]*B2[-1])-abs(Bm[0]*B2[0])=0:
  print(ansC)
elif abs(Bp[-1]*B2[-1])-abs(Bm[0]*B2[0])>0:
  print(ansB)
else: print(ansB)

#print(max(ansB,ansC))


### FIXED CODE ###

import numpy as np
N,K=map(int, input().split())
A =list(map(int,input().split()))
MOD = 10 ** 9 + 7
if N==K:
  ans0 = 1
  for a in A[0:N]:
    ans0 *= a
    ans0 %= MOD
  print(ans0)
  exit()
A=sorted(A)  
if (K%2==1 and A[-1]<0):
  ans1 = 1
  for a in A[N-K:N]:
    ans1 *= a
    ans1 %= MOD
  print(ans1)
  exit()
 
A=sorted(A, key=lambda x:abs(x), reverse=True)
AA=[np.sign(i) for i in A]
 
ansA = 1
for a in A[0:K]:
  ansA *= a
  ansA %= MOD
ansAA = AA[0:K].count(-1)%2
if ansA==0 or ansAA==0:
  print(ansA)
  exit()

while ansA>0:
  ansA-=MOD

B1=A[0:K]
C1=A[0:K]
B2=sorted(A[K:N])
Bp=[i for i in A[0:K] if i>0]
Bm=[i for i in A[0:K] if i<0]
 
if B2[0]>0:B2.insert(0,0)
if B2[-1]<0:B2.insert(-1,0)
if not Bp:Bp.insert(0,B1[-1])
if not Bm:Bm.insert(0,B1[0])
  
#print(Bp,Bm,B2)
#print(Bp[-1],B2[0])
B1.remove(Bp[-1])
B1.append(min(B2[0],0))
#print(B1)
ansB = 1
for a in B1[0:K]:
  ansB *= a
  ansB %= MOD
#print(Bm[-1],B2[-1])
C1.remove(Bm[-1])
C1.append(max(B2[-1],0))
 
ansC = 1
for a in C1[0:K]:
  ansC *= a
  ansC %= MOD
#print(B1,C1)
#print(ansB,ansC)
BB1=[np.sign(i) for i in B1]
ansBB1 = BB1[0:K].count(-1)%2
BB2=[np.sign(i) for i in C1]
ansBB2 = BB2[0:K].count(-1)%2
#print(ansBB1,ansBB2)
if ansBB1==1:
  print(ansC)
  exit()
if ansBB2==1:
  print(ansB)
  exit()
#print(B2[0]/Bp[-1],B2[-1]/Bm[-1])
#print(Bp[-1]*B2[-1],Bm[0]*B2[0])

#print(abs(Bp[-1]*B2[-1])-abs(Bm[-1]*B2[0]))
#print(ansB,ansC)
if abs(Bp[-1]*B2[-1])-abs(Bm[-1]*B2[0])>=0:
  print(ansC)
else: print(ansB)
#A
s = input()

if s == ABC:
    print('ARC')
else:
    print('ABC')

### FIXED CODE ###

#A
s = input()

if s == 'ABC':
    print('ARC')
else:
    print('ABC')
import math

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

print(math.ceil(N / (D * 2 + 1)))

### FIXED CODE ###

input_ = int(input())

print(3 * input_ ** 2)
n = int(input())
p = map(int, input().split())
k = int(input())
s = sum(p)
for i in range(k):
  a, b = map(int, input().split())
  print(s - p[a-1] + b)


### FIXED CODE ###

a, op, b = input().split()
a = int(a)
b = int(b)
if op == "+":
  print(a + b)
else:
  print(a - b)
N, X = map(int, input().split())
x = list(map(int, input().split()))

xdef = [abs(x[i]-X) for i in range(N)]
def gcd(m,n):
  x = max(m,n)
  y = min(m,n)
  if x%y == 0:
    return y
  else:
    while x%y != 0:
      z = x%y
      x = y
      y = z
    else:
      return z
    
tmp = gcd(xdef[0], xdef[1])
for i in range(2,N):
  gcd = gcd(tmp,xdef[i])
print(gcd)

### FIXED CODE ###

N, X = map(int, input().split())
x = list(map(int, input().split()))

xdef = [abs(x[i]-X) for i in range(N)]
def gcd(m,n):
  x = max(m,n)
  y = min(m,n)
  if x%y == 0:
    return y
  else:
    while x%y != 0:
      z = x%y
      x = y
      y = z
    else:
      return z

if N == 1:
  print(xdef[0])
else:
  tmp = gcd(xdef[0], xdef[1])
  for i in range(1,N):
    tmp = gcd(tmp,xdef[i])
  print(tmp)
# https://atcoder.jp/contests/abc096/tasks/abc096_c

H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

# 隣に # が一つ以上あるかどうか
def has_neighbor(y, x):
    dhs = [1, -1, 0, 0]
    dws = [0, 0, 1, -1]
    for dh, dw in zip(dhs, dws):
        if S[y + dh][x + dw] == "#":
            return True
    return False


for h in range(H):
    for w in range(W):
        if S[h][w] == "#":
            if not has_neighbor(h, w):
                print("No")
                exit()

print("Yes")




### FIXED CODE ###

# https://abc096.contest.atcoder.jp/tasks/abc096_c

neighbor_i = [-1, 0, 1, 0]
neighbor_j = [0, -1, 0, 1]

H, W = map(int, input().split())


def can_draw(l, target_i, target_j):
    for i, j in zip(neighbor_i, neighbor_j):
        if target_i + i < 0 or target_j < 0:
            continue
        if target_i + i >= H or target_j + j >= W:
            continue
        if l[target_i + i][target_j + j] == '#':
            return True

    return False


data = []
for i in range(H):
    raw = list(str(input()))
    data.append(raw)


# print(data)


ok = True
for i in range(H):
    for j in range(W):
        if data[i][j] == '#':
            if not can_draw(data, i, j):
                ok = False
                break
    if not ok:
        break

if ok:
    print('Yes')
else:
    print('No')
a,b,c=map(int,input().split())
import math
if 4*a*b<(c-a-b)**2 and c-a-b>=0
  print('Yes')
else:
  print('No')


### FIXED CODE ###

a,b,c=map(int,input().split())
import math
if 4*a*b<(c-a-b)**2 and c-a-b>=0:
  print('Yes')
else:
  print('No')
a, b, c = map(int, input().spulit())
if a / c = b:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

d,t,s=map(int,input().split())
if d<=t*s:
    print("Yes")
else:
    print("No")
import math
def f(n):
    res = 0
    while(n%2 == 0):
        res += 1
        n //= 2
    return res

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

n, m = map(int, input().split())
a = list(map(lambda x: int(x) // 2, input().split()))

t = f(a[0])
for v in a:
    if(f(v) != t):
        print(0)
        exit()
a = list(map(lambda x: x >> t, a))
m >>= t

l = 1
for v in a:
    l = lcm(l, v)
    if(l > m ):
        print(0)
        exit()
ans = - (-m // (2*l))
print(ans)

### FIXED CODE ###

from functools import reduce
def f(n):
    res = 0
    while(n%2 == 0):
        res += 1
        n //= 2
    return res

def gcd(a, b):
    return a if b == 0 else gcd(b, a%b)

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

n, m = map(int, input().split())
A = list(map(lambda x: int(x) // 2, input().split()))

l = reduce(lcm, A, 1)
for a in A:
    if((l // a) % 2 == 0):
        print(0)
        break

else:
    ans = (m // l +1) // 2
    print(ans)
def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

x = int(input())  
  
while not is_prime(x):
  x+=1
  
print(x)  

### FIXED CODE ###

import math

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

x = int(input())  
  
while not is_prime(x):
  x+=1
  
print(x)
a , b , c , d = input().split()

a=int(a)
b=int(b)
c=int(c)
d=int(d)

while True:
  c -= b
  if c <= 0:
    print('Yes')
    break
  a -= d
  if a <= 0:
    print('No')
    break



### FIXED CODE ###

a ,b = input().split()

a=int(a)
b=int(b)
if a>b:
	print('safe')
else:
	print('unsafe')
import sys
s = input()
gx,gy = map(int, input().split(' '))
x_d = [0]
y_d = []
cnt = 0
for i in range(len(s)):
    if s[i] == "T":
        cnt += 1
        if cnt % 2 == 0:
            x_d.append(0)
        elif cnt % 2 == 1:
            y_d.append(0)
    if s[i] == "F":
        if cnt % 2 == 0:
            x_d[-1] += 1
        elif cnt % 2 == 1:
            y_d[-1] += 1
x_d.append(0)
y_d.append(0)
if (sum(x_d)-gx) % 2 or (sum(y_d)-gy) % 2:
    print("No")
    sys.exit()
x_n = (sum(x_d)-gx)//2
y_n = (sum(y_d)-gy)//2
DPx = [[False for i in range(x_n+1)] for j in range(len(x_d))]
DPy = [[False for i in range(y_n+1)] for j in range(len(y_d))]
for x in DPx:
    x[0] = True
for y in DPy:
    y[0] = True
for i in range(len(x_d)-1):
    for j in range(x_n+1):
        if DPx[i][j]:
            DPx[i+1][j] = True
            if j+x_d[i] <= x_n:
                DPx[i+1][j+x_d[i]] = True
for i in range(len(y_d)-1):
    for j in range(y_n+1):
        if DPy[i][j]:
            DPy[i+1][j] = True
            if j+y_d[i] <= y_n:
                DPy[i+1][j+y_d[i]] = True

if DPx[len(x_d)-1][x_n] and DPy[len(y_d)-1][y_n]:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

import sys
s = input()
gx,gy = map(int, input().split(' '))
x_d = [0]
y_d = []
cnt = 0
for i in range(len(s)):
    if s[i] == "T":
        cnt += 1
        if cnt % 2 == 0:
            x_d.append(0)
        elif cnt % 2 == 1:
            y_d.append(0)
    if s[i] == "F":
        if cnt % 2 == 0:
            x_d[-1] += 1
        elif cnt % 2 == 1:
            y_d[-1] += 1
gx -= x_d[0]
x_d[0] = 0
x_d.append(0)
y_d.append(0)
if (sum(x_d)-gx) % 2 or (sum(y_d)-gy) % 2 or sum(x_d) < abs(gx) or sum(y_d) < abs(gy):
    print("No")
    sys.exit()
x_n = (sum(x_d)-gx)//2
y_n = (sum(y_d)-gy)//2
DPx = [[False for i in range(x_n+2)] for j in range(len(x_d))]
DPy = [[False for i in range(y_n+2)] for j in range(len(y_d))]
for x in DPx:
    x[0] = True
for y in DPy:
    y[0] = True
for i in range(len(x_d)-1):
    for j in range(x_n+1):
        if DPx[i][j]:
            DPx[i+1][j] = True
            if j+x_d[i] <= x_n+1:
                DPx[i+1][j+x_d[i]] = True
for i in range(len(y_d)-1):
    for j in range(y_n+1):
        if DPy[i][j]:
            DPy[i+1][j] = True
            if j+y_d[i] <= y_n+1:
                DPy[i+1][j+y_d[i]] = True
if DPx[len(x_d)-1][x_n] and DPy[len(y_d)-1][y_n]:
    print("Yes")
else:
    print("No")
q = int(input())

def Longest_Common(q) :
    X = raw_input()
    Y = raw_input()
    dp = [ [0 for i in range( len(X) )] for j in range( len(Y) )] #???X??????Y?????????????????????
    
    for j in range( len(Y) ):
        if Y[j] == X[0] :
            dp[j][0] += 1
        if( j+1 <= len(Y) - 1 ) :
            dp[j+1][0] = dp[j][0]

    for i in range( 1,len(X) ):
        if X[i] == Y[0] :
            dp[0][i] += 1
        if( i+1 <= len(X) - 1 ) :
            dp[0][i+1] = dp[0][i+1]
        
    for i in range( 1,len(X) ): 
        for j in range( 1,len(Y) ):
            if X[i] == Y[j] : dp[j][i] = max( dp[j-1][i-1], dp[j-1][i], dp[j][i-1]) + 1 
            else : dp[j][i] = max( dp[j-1][i-1], dp[j-1][i], dp[j][i-1])
                
    print dp[ len(Y)-1 ][ len(X)-1 ]    
    
    if( q == 1 ) :
        return
    else :
        Longest_Common(q-1)
        
Longest_Common(q)

### FIXED CODE ###

def solve():
    seq1 = raw_input()
    seq2 = raw_input()
  
    a, b = len(seq1), len(seq2)
    x1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = seq1[i]
        x2 = x1+[]
        for j in range(b):
            if e1 == seq2[j]:
                x1[j+1] = x2[j] + 1
            elif x1[j+1] < x1[j]:
                x1[j+1] = x1[j]
    return x1[-1]
  
n = input()
for i2 in range(n):
    print solve()
N=int(input())
C = Counter(map(int, input().split()))
dp = [[[.0] * (N + 2) for _ in range(N + 2)] for _ in range(N + 2)]
for i in range(C[3] + 1):
    for j in range(N - C[1] - i + 1):
        for k in range(N - i - j + 1):
            if i + j + k != 0:
                dp[i][j][k] = (
                    N +
                    i * dp[i - 1][j + 1][k] +
                    j * dp[i][j - 1][k + 1] +
                    k * dp[i][j][k - 1]
                ) / (i + j + k)
                print(dp)
                print(' ')
print(dp[C[3]][C[2]][C[1]])

### FIXED CODE ###

N=int(input())
C=[0]*4
for i in map(int, input().split()):
    if i==1:
        C[1]+=1
    elif i==2:
        C[2]+=1
    else:
        C[3]+=1
dp = [[[.0] * (N + 2) for _ in range(N + 2)] for _ in range(N + 2)]
for i in range(C[3] + 1):
    for j in range(N - C[1] - i + 1):
        for k in range(N - i - j + 1):
            if i + j + k != 0:
                dp[i][j][k] = (
                    N +
                    i * dp[i - 1][j + 1][k] +
                    j * dp[i][j - 1][k + 1] +
                    k * dp[i][j][k - 1]
                ) / (i + j + k)
print(dp[C[3]][C[2]][C[1]])
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()))

ab_total_list = []
total_list = []

for i in A:
    for j in B:
        ab_total_list.append(i+j)
C.sort()
C.reverse()
ab_total_list.sort()
ab_total_list.reverse()

z = 0
min_total = 0
if K > len(ab_total_list):
    min_total = ab_total_list[-1]
else:
    min_total = ab_total_list[K]

for i in ab_total_list:
    for j in C:
        total = i + j
        if z > K+2 and min_total > total:
            break
        total_list.append(i+j)
    min_total = total_list[-1]

total_list.sort()
total_list.reverse()
for i in range(0, K):
    print(total_list[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()))

ab_total_list = []
total_list = []

A.sort()
A.reverse()
if len(A) > K:
    A = A[0:K+1]

B.sort()
B.reverse()
if len(B) > K:
    B = B[0:K+1]

C.sort()
C.reverse()
if len(C) > K:
    C = C[0:K+1]

ab_total_list = []
for i in A:
    for j in B:
        ab_total_list.append(i+j)

ab_total_list.sort()
ab_total_list.reverse()
if len(ab_total_list) > K:
    ab_total_list = ab_total_list[0:K+1]

for i in range(0, K):
    for j in range(0, int(K/(i+1))):
        if j >= len(C) or i >= len(ab_total_list):
            break
        total = ab_total_list[i] + C[j]
        total_list.append(total)
        if (i*j) > K:
            break

total_list.sort()
total_list.reverse()
for i in range(0, K):
    print(total_list[i])
x*x*x

### FIXED CODE ###

x=int(input())
print(x**3)
n = int(input())
p = list(map(int, input().split()))

ans = 0
for i in range(n):
    if p[i] == i+1:
        p[i+1] = p[i]
        ans += 1

print(ans)

### FIXED CODE ###

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

ans = 0
for i in range(n-1):
    if p[i] == i+1:
        p[i+1] = p[i]
        ans += 1

if p[n-1] == n:
    ans += 1
print(ans)