Harryxun/stf_run huggingface dataset:
def cmin(a,b):
    if a>b:
        return b
    else:
        return a

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

dp = [0] + [float("inf")]*(N-1)
for i in range(1,N):
    for j in range(1, min(i+1,K+1)):
        dp[i] = cmin(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
print(dp)


### FIXED CODE ###

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

cost = [0]
for i in range(2,N+1):
    cost.append( min([cost[j] + abs(h[i-1]-h[j]) for j in range(max(0,i-K-1), i-1)]) )
print(cost[-1])
def sol(lis):
    if len(lis)<=2:
        return abs(lis[0]-lis[1])
    costs = [0,abs(lis[0]-lis[1])]
    for i in range(2,len(lis)):
        x = abs(lis[i]-lis[i-1])
        y = abs(lis[i]-lis[i-2])
        costs.append(min(x+costs[-1]),min(x+costs[-2]))
    print(costs)
    return costs[-1]
input()
lis = list(map(int,input().split(' ')))
print(sol(lis))

### FIXED CODE ###

def sol(lis):
    if len(lis)<=2:
        return abs(lis[0]-lis[1])
    costs = [0,abs(lis[0]-lis[1])]
    for i in range(2,len(lis)):
        x = abs(lis[i]-lis[i-1])
        y = abs(lis[i]-lis[i-2])
        costs.append(min(x+costs[-1],y+costs[-2]))
    return costs[-1]
input()
lis = list(map(int,input().split(' ')))
print(sol(lis))
n=int(input())

result=[]

for i in range(1,n+1):
    if i %3==0:
        result.append(i)
    else:
        k=i
        for j in range(1,len(str(n)+1):
            if k%(10**j)==3:
                result.append(i)
                break
            else:
                k=k//(10**j)
        else:
            continue

print(" ", *result)

### FIXED CODE ###

n=int(input())
 
result=[]
for i in range(1,n+1):
    if i %3==0:
        result.append(i)
    else:
        k=i
        for j in range(1,5):
            if k%10==3:
                result.append(i)
                break
            else:
                k=k//10
        else:
            continue
 
print("",*result)
import numpy as np
from fractions import gcd
from functools import reduce

LARGE_INT = 10 ** 9 + 7

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

input()
A = list(map(int, input().split()))
lcm = lcm_list(A)

total = 0
for a in A:
    total += lcm // a % LARGE_INT
    total %= LARGE_INT
print(total)

### FIXED CODE ###

import sys
from fractions import gcd

input = sys.stdin.buffer.readline

LARGE = 10 ** 9 + 7

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

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

l = 1
for a in A:
    l = lcm(l, a)

total = 0
for a in A:
    total += l // a

print(total % LARGE)
import bisect

n,k= map(int,input().split())
x = [int(i) for i in input().split()]

idx = bisect.bisect_left(x,0)
"""
if x[idx] == 0:
    x.insert(idx,0)
"""

ans = 10**100

print(x[idx])

print(ans)
exit()

for i in range(k+1):
    #print(idx-i,idx+k-1-i)
    if i == 0 and idx+k-1 < n:
        ans = min(ans, x[idx+k-1])
    elif idx - i < 0 or idx+k-1-i >= n:
        continue
    else:
        ans = min(ans, - 2*x[idx-i] + x[idx+k-1-i])
        ans = min(ans, - x[idx-i] + 2*x[idx+k-1-i])

print(ans)

### FIXED CODE ###

import bisect

n,k= map(int,input().split())
x = [int(i) for i in input().split()]

idx = bisect.bisect_left(x,0)
"""
if x[idx] == 0:
    x.insert(idx,0)
"""
ans = 10**100


for i in range(k+1):
    #print(idx-i,idx+k-1-i)
    if i == 0 and idx+k-1 < n:
        ans = min(ans, x[idx+k-1])
    elif idx - i < 0 or idx+k-1-i >= n:
        continue
    else:
        ans = min(ans, - 2*x[idx-i] + x[idx+k-1-i])
        ans = min(ans, - x[idx-i] + 2*x[idx+k-1-i])

if idx == n:
    ans = -x[-k]

print(ans)
import sys
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
V = [None]*N
E = []
for n in range(N):
	V[n] = list(map(int,inputs().split()))
	V[n][0] -= V[n][2]
	V[n][1] -= V[n][2]
	E.append([V[n][0],1,V[n][2]])
	E.append([V[n][1],-1,V[n][2]])
D = [int(inputs()) for p in [0]*Q]
E.sort(key = lambda x:x[0])
mini = 1000000001
kouho = [1000000001]
q = 0
d = D[0]
for e in E:
	flag = 0
	if e[0] <= d:
		if  e[1] == 1:
			kouho.append(e[2])
		elif e[1] == -1:
			kouho.remove(e[2])
	if e[0] > d:
		for k in kouho:
			mini = min(k,mini)
		if mini < 1000000001:
			print(mini)
			mini = 1000000001
		else:
			print(-1)
			mini = 1000000001
		flag = 1
		if q < Q-1:
			q = q + 1
			d = D[q]
		else:
			break
	if e[0] <= d and flag == 1:
		if  e[1] == 1:
			kouho.append(e[2])
		elif e[1] == -1:
			kouho.remove(e[2])
for t in [None]*(Q-q):
	print(-1)

### FIXED CODE ###

import sys
from operator import itemgetter
def main():
	inputs = sys.stdin.readline
	N, Q= map(int,inputs().split())
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while e[0] > d:
			if cont == True:
				print(mini-(mini//1000000001)*1000000002)
			else:
				mini = min(kouho)
				print(mini-(mini//1000000001)*1000000002)
			cont = True
			q = q + 1
			if q > Q-1:
				flag = True
				break
			d = int(inputs())
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			if mini == e[2]:
				cont = False
	for t in [None]*(Q-q):
		print(-1)
main()
N = int(input())
luca = [2, 1]

for i in range(101):
    luca.append(luca[i]+luca[i+1])

print(luca[N])


### FIXED CODE ###

N = input()

cnt = 1

for i in range(len(N)-1):

    if N[i] == N[i+1]:
        cnt += 1

    else:
        cnt = 1

    if cnt == 3:
        print("Yes")
        exit()


print("No")
from collections import defaultdict
import sys
input = sys.stdin.readline
N, Q = map(int,input().split())
edge_from = defaultdict(list)
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edge_from[a].append(b)
tmp = [0]*N
for i in range(Q):
    p, x = map(int,input().split())
    tmp[p-1] += x
q = [None]*N
head = 0
tail = 1
q[0] = (0, 0)
while head < N:
    p, x = q[head]
    x += tmp[p]
    tmp[p] = x
    head += 1
    for nx in edge_from[p]:
        q[tail] = (nx, x)
        tail += 1
print(*tmp)

### FIXED CODE ###

import sys
from collections import defaultdict
sys.setrecursionlimit(1000000)
N, Q = map(int,input().split())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)

d = defaultdict(int)
for _ in range(Q):
    p,x = map(int,input().split())
    d[p-1] += x
visited = [False]*N
cnt = [0]*N
def dfs(n, acc):
    cnt[n] = acc
    for m in edges[n]:
        if not visited[m]:
            visited[m] = True
            dfs(m, acc+d[m])
visited[0] = True
dfs(0, d[0])
print(*cnt)
from collections import defaultdict


def eratosthenes_generator():
    yield 2
    n = 3
    h = {}
    while True:
        m = n
        if n in h:
            b = h[n]
            m += 2 * b
            while m in h:
                m += 2 * b
            h[m] = b
            del h[n]
        else:
            m += 2 * n
            while m in h:
                m += 2 * n
            h[m] = n
            yield n
        n += 2


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


def prime_factorize(n):
    f = defaultdict(lambda: 0)
    k = n
    for p in eratosthenes_generator():
        while True:
            d, m = divmod(k, p)
            if m == 0:
                f[p] += 1
                k = d
            else:
                break
        if k == 1:
            break
    return f


MOD = 1000000007
n, m = map(int, input().split())
pf = prime_factorize(m)
mx = max(pf.values())
f, r = prepare(n + mx, MOD)
ans = 1
for p, e in pf.items():
    ans *= f[n + e - 1]
    ans %= MOD
    ans *= r[n - 1]
    ans %= MOD
    ans *= r[e]
    ans %= MOD
print(ans)


### FIXED CODE ###

from collections import defaultdict


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


def prime_factorize(n):
    f = defaultdict(lambda: 0)
    f[2] = len(bin(n & -n)) - 3
    i = 3
    k = n >> f[2]
    while k > 1:
        while True:
            d, m = divmod(k, i)
            if m == 0:
                f[i] += 1
                k = d
            else:
                break
        i += 2
    return f


MOD = 1000000007
n, m = map(int, input().split())
pf = prime_factorize(m)
mx = max(pf.values())
f, r = prepare(n + mx, MOD)
ans = 1
for p, e in pf.items():
    ans *= f[n + e - 1] * r[n - 1]
    ans %= MOD
    ans *= r[e]
    ans %= MOD
print(ans)
n,q = map(int,input().split())
s = list(input())
cum = [0 for i in range(n+1)]
i = 0
while i < n:
    if s[i] == "A" and s[i+1] == "C":
        cum[i+1] = cum[i]
        cum[i+2] = 1+cum[i+1]
        i += 2
    else:
        cum[i+1] = cum[i]
        i += 1

for i in range(q):
    l,r = map(int,input().split())
    print(cum[r]-cum[l])

### FIXED CODE ###

n,q = map(int,input().split())
s = list(input())
cum = [0 for i in range(n+1)]
i = 0
while i < n:
    if i < n-1 and s[i] == "A" and s[i+1] == "C":
        cum[i+1] = cum[i]
        cum[i+2] = 1+cum[i+1]
        i += 2
    else:
        cum[i+1] = cum[i]
        i += 1

for i in range(q):
    l,r = map(int,input().split())
    print(cum[r]-cum[l])
N = int(input())
print(sum([i for i in range(1, N+1)])

### FIXED CODE ###

N = int(input())
print(sum([i for i in range(1, N+1)]))
n = input()
op_cnt = len(n) - 1  # すき間の個数
for i in range(2 ** op_cnt):
    op = ["-"] * op_cnt  # あらかじめ ["-", "-", "-"] というリストを作っておく
    for j in range(op_cnt):
        if ((i >> j) & 1):
            op[op_cnt - 1 - j] = "+"  # フラグが立っていた箇所を "+" で上書き

    formula = ""
    for p_n, p_o in zip(n, op + [""]):  # 少々モヤッとする
        formula += (p_n + p_o)
    if eval(formula) == 7:
        print(formula + "=7")
        break

### FIXED CODE ###

n = list(raw_input())
operators = ["+", "-"]
total = None
for op1 in operators:
    for op2 in operators:
        for op3 in operators:
            total = n[0] + op1 + n[1] + op2 + n[2] + op3 + n[3]
            if eval(total) == 7:
                total = total + "=7"
                print(total)
                exit(0)
s=list(map(int,input().split("/")))
if (s[0]=2019 and s[1]<=4) or (s[0]<2019):
  print("Heisei")
else:
  print("TBD")

### FIXED CODE ###

s=list(map(int,input().split("/")))
if (s[0]==2019 and s[1]<=4) or (s[0]<2019):
  print("Heisei")
else:
  print("TBD")
n = int(input())
fib = [1, 1]
for i in range(n):
    fib[i] = fib[i-1] + fib[i-2]
print(fib[n])

### FIXED CODE ###

n = int(input())
fib = [1, 1] + [0] * n
for i in range(2, n+1):
    fib[i] = fib[i-1] + fib[i-2]
print(fib[n])
A,B,C,D,E,F = map(int, input().split())

import functools

@functools.lru_cache(maxsize=None)
def calc_strength(sugar, water):
    if water == 0: return -1
    return sugar * 100 / (sugar + water)

@functools.lru_cache(maxsize=None)
def f(strength, sugar, water):
    cand = []
    for x in ((C, 0), (D, 0), (0, 100*A), (0, 100*B)):
        s, w = sugar + x[0], water + x[1]
        if s + w <= F and s * 100 <= w * E:
            cand.append(f(calc_strength(s, w), s, w))
    if cand: return sorted(cand, reverse=True)[0]
    return (strength, sugar + water, sugar)
    
print(f(-1, 0, 0)[1:])

### FIXED CODE ###

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

import functools
import sys
sys.setrecursionlimit(10**5)

@functools.lru_cache(maxsize=None)
def calc_strength(sugar, water):
    if water == 0: return -1
    return sugar * 100 / (sugar + water)

@functools.lru_cache(maxsize=None)
def f(strength, sugar, water):
    cand = [(strength, sugar + water, sugar)]
    for x in ((C, 0), (D, 0), (0, 100*A), (0, 100*B)):
        s, w = sugar + x[0], water + x[1]
        if s + w <= F and s * 100 <= w * E:
            cand.append(f(calc_strength(s, w), s, w))
    return max(cand)
    
print(*f(-1, 0, 0)[1:])
dish=[int(input()) for _ in range(5)]
count={str(i%10):[] for i in range(10,-1,-1)}
for t in dish:
	one=t%10
	count[str(one)].append(t)

ans=0
d=0
for k,v in count.items():
	if v!=[]:
		for c in v:
			if d>3:
				ans+=c
			else:
				ans+=math.ceil(c/10)*10
				d+=1
print(int(ans))

### FIXED CODE ###

import math

dish=[int(input()) for _ in range(5)]
count={str(i%10):[] for i in range(10,-1,-1)}
for t in dish:
	one=t%10
	count[str(one)].append(t)

ans=0
d=0
for k,v in count.items():
	if v!=[]:
		for c in v:
			if d>3:
				ans+=c
			else:
				ans+=math.ceil(c/10)*10
				d+=1
print(int(ans))
N = int(input())
p = list(map(int, input().split()))
cnt = 0
for n in range(N):
    if p[n] != n+1:
        cnt+=1

if cnt <= 2:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

a, b = map(int, input().split())
if (a + b) % 2 != 0:
    print("IMPOSSIBLE")
else:
    print(int((a+b)/2))
N,X,T=map(int,input().split())
if N%X ==0:
  print(NT/x)
else:
  print((N/X+1)*T)

### FIXED CODE ###

N,X,T=map(int,input().split())
if N%X ==0:
    print(N*T//X)
else:
    print(((N//X)+1)*T)
s = list(input())
answer = []

for i range s:
        if  i == "B":
            try:
                answer.pop()
            except:
                pass
        else:
            answer.append(i)

print("".join(answer))

### FIXED CODE ###

s = list(input())
answer = []

for i in s:
        if  i == "B":
            try:
                answer.pop()
            except IndexError:
                pass
        else:
            answer.append(i)

print("".join(answer))
import sys
input = sys.stdin.readline
from collections import Counter
import math
def main():
    N, P = map(int, input().split())
    S = input().rstrip("\r\n")[::-1]
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            if int(S[i]) % P == 0:ans += N-i
    else:
        D = [0] * (N+1)
        for i in range(1, N+1):
            D[i] = ((int(S[i-1])*int(math.pow(10, i-1))) % P + D[i-1]) % P
        c = Counter(D)
        for v in c.values():
            ans += v*(v-1)//2
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import Counter
def main():
    N, P = map(int, input().split())
    S = list(map(int, input().rstrip("\r\n")))
    S.reverse()
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            if S[i] % P == 0:ans += N-i
    else:
        A = [0] * N
        tenpow = 1
        for i in range(N):
            A[i] = (S[i]*tenpow) % P
            tenpow *= 10
            tenpow %= P
        D = [0] * (N+1)
        for i in range(N):
            D[i+1] = (D[i] + A[i]) % P
        c = Counter(D)
        for v in c.values():
            ans += v*(v-1)//2
    print(ans)
if __name__ == "__main__":
    main()
a = int(input())
b = int(input())

if a<=8 and b<=8 :
    print("Yay!")
else:
    print(":(")

### FIXED CODE ###

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

if a<=8 and b<=8 :
    print("Yay!")
else:
    print(":(")
n = int(input())
h = list(map(int, input().split()))

dp = []
for i in range(n):
    dp.append(-1)


def flog(m):
    if dp[m] >= 0:
        return dp[m]
    if m == 0:
        dp[m] = 0
        return 0
    if m == 1:
        dp[m] = abs(h[0]-h[1])
        return dp[m]
    else:
        dp[m] = min(flog(m-1) + abs(h[m-1] - h[m]),flog(m-2) + abs(h[m-2] - h[m]))
        return dp[m]
  
print(flog(n-1))

### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))
 
dp = []
for i in range(n):
	dp.append(int(0))
dp[0] = 0
dp[1] = abs(h[0]-h[1])
 
for j in range(2,n):
	dp[j] = min(dp[j-1] + abs(h[j-1] - h[j]),dp[j-2] + abs(h[j-2] - h[j]))
  
print(dp[n-1])
X,Y=map(int,input().split);
print(int(x+Y/2));

### FIXED CODE ###

X,Y=map(int,input().split())
print(int(X+Y/2))
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 math

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

if (X + Y) % 3 != 0:
  print(0)
  
else:
  a = Y - (X + Y) // 3
  b = X - (X + Y) // 3
  total = a + b
  m = min(a,b)
  def permod(n, r):
    return (math.factorial(n) // math.factorial(n - r)) % (10 ** 9 + 7)
  
  ans = permod(total,m)
  print(ans)

### FIXED CODE ###

r = int(input())

print(r ** 2)
import math

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


a,b,c,d = map(int,input().split())
not_a_1 =0
not_b = 0
not_b =  b-(b//c)-(b//d)+(b//lcm(c,d))
not_a_1 = a-1-((a-1)//c)-((a-1)//d)+((a-1)//lcm(c,d))

print(not_b-not_a_1)

### FIXED CODE ###

import fractions

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


a,b,c,d = map(int,input().split(' '))
not_a_1 =0
not_b = 0
not_b =  b-(b//c)-(b//d)+(b//lcm(c,d))
not_a_1 = a-1-((a-1)//c)-((a-1)//d)+((a-1)//lcm(c,d))

print(not_b-not_a_1)
n,l = (int(I) for i in input().split())
d = (l-1)*n+(n+1)*n//2
if l<1: print(d+1-l-min(n,1-l))
else: print(d-l)

### FIXED CODE ###

n,l = (int(i) for i in input().split())
d = (l-1)*n+(n+1)*n//2
if l<1: print(d+1-l-min(n,1-l))
else: print(d-l)
from itertools import combinations
from collections import Counter

N = int(input())
xy = [tuple(map(int, input().split())) for _ in range(N)]

delta = []
for i, j in combinations(list(range(N)), 2):
    if xy[i][0] < xy[j][0]:
        p0 = xy[i][:]
        p1 = xy[j][:]
    else:
        p0 = xy[j][:]
        p1 = xy[i][:]
    delta.append((p1[0] - p0[0], p1[1] - p0[1]))
cnt = Counter(delta)

dlt = cnt.most_common()[0][0]

visited =set()
c = 0

for i in range(N):
    if xy[i] in visited:continue
    c += 1
    temp = [[xy[i], c]]
    while temp:
        q = temp.pop()
        for n in [1, -1]:
            x1, y1 = q[0][0] + n * dlt[0], q[0][1] + n * dlt[1]
            if not (x1, y1) in visited and (x1, y1) in xy:
                temp.append([(x1, y1), q[1]])
                visited.add((x1, y1))

print(c)
                
    
    


### FIXED CODE ###

from itertools import combinations
from collections import Counter

N = int(input())
xy = [tuple(map(int, input().split())) for _ in range(N)]

if N != 1:
    delta = []
    for i, j in combinations(list(range(N)), 2):
        if xy[i][0] < xy[j][0]:
            p0 = xy[i][:]
            p1 = xy[j][:]
        else:
            p0 = xy[j][:]
            p1 = xy[i][:]
        delta.append((p1[0] - p0[0], p1[1] - p0[1]))
    cnt = Counter(delta)
    dlt = cnt.most_common()
    
def calc(dd):
    visited =set()
    c = 0
    for i in range(N):
        if xy[i] in visited:continue
        c += 1
        temp = [[xy[i], c]]
        while temp:
            q = temp.pop()
            for n in [1, -1]:
                x1, y1 = q[0][0] + n * dd[0], q[0][1] + n * dd[1]
                if not (x1, y1) in visited and (x1, y1) in xy:
                    temp.append([(x1, y1), q[1]])
                    visited.add((x1, y1))
    return c

if N == 1: print(1)
else:
    ans = []
    pre = dlt[0][1]
    for lst in dlt:
        ans.append(calc(lst[0]))
    print(min(ans))
import math

a,b,c,d = map(int,input().split())
if (math.ceil(a/d)) <= (math.ceil(b/c)):
    print('No')
else:
    print('Yes')


### FIXED CODE ###

a, b = map(int,input().split())
if a <= b:
    print('unsafe')
else:
    print('safe')
import math

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

ceil = math.ceil

max_a = max(a)
target_length = max_a//2 + 1
min_a = 0




while True:
    cnt = 0
    for a in A:
        cut_num = (a + target_length - 1)//target_length
        cnt += cut_num
    if cnt > k:
        min_a = target_length
        target_length = (target_length + max_a)//2
    else:
        if target_length - min_a == 1:
            print(target_length)
            exit()
        max_a = target_length
        target_length = (target_length + min_a)//2

### FIXED CODE ###

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

max_a = max(A)
min_a = 0

while abs(max_a - min_a) > 1:
    cnt = 0
    target_length = (max_a + min_a)//2
    for a in A:
        cut_num = (a + target_length - 1)//target_length
        cnt += cut_num - 1
    if cnt > k:
        min_a = target_length
    else:
        if target_length - min_a == 1:
            print(target_length)
            exit()
        max_a = target_length

print(max_a)
n=int(input())
a=list(map(int,input().split()))
m=0
def yakusu(x):
  lst=[]
  for i in range(x**(0.5)):
    if x%i==0:
      lst.append(i)
      lst.append(x//i)
  return lst    
for i in range(n):
  for j in range(len(yakusu(a[i]))):
    while yakusu(a[i])[j]%2==0:
      yakusu(a[i])[j]==yakusu(a[i])[j]//2
      m+=1
print(m)

  


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
m=0
for i in range(n):
  while a[i]%2==0:
    a[i]=a[i]//2
    m+=1
print(m)
import math
??
a, b, C = input().split()
a = float(a)
b = float(b)
C = float(C)
??
c = math.sqrt(((a*a) + (b*b) - 2*a*b*math.cos(math.radians(C))))
L = a + b + c
S = a*b*math.sin(math.radians(C))/2
h = 2*S/a
print("%.5f\n%.5f\n%.5f" % (S, L, h))

### FIXED CODE ###

import math as m

a,b,c=input().split()
a=int(a)
b=int(b)
c=int(c)
c=m.radians(c)
S=0.5*a*b*m.sin(c)
L=a+b+m.sqrt(a*a+b*b-2*a*b*m.cos(c))
H=b*m.sin(c)
print(S)
print(L)
print(H)
import itertools

q = int(input())
for a in range(q):
    X = input()
    Y = input()
    cost = [0]
    for c in Y:
        for i in range(len(cost) - 1, -1, -1):
            index = X.find(c, cost[i]) + 1
            if index:
                if i + 1 < len(cost):
                    cost[i + 1] = min(cost[i + 1], index)
                else:
                    cost.append(index)
    print(len(cost) - 1)

### FIXED CODE ###

def solve():
    a1 = raw_input()
    a2 = raw_input()
    a = len(a1)
    b = len(a2)
    c1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = a1[i]
        c2 = c1+[]
        for j in range(b):
            if e1 == a2[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()