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

param_x, param_k, param_d = map(int, input().split())

param_x_tmp = param_x

if param_x > 0:
  int_times_nega_posi = -1
else:
  int_times_nega_posi =  1

count = 0
while param_x_tmp*param_x > 0:
  
  param_x_tmp = param_x_tmp + param_d*int_times_nega_posi
  
  count = count + 1
  
  if count == param_k:
    print(abs(param_x_tmp))

if count < param_k:
  int_move = param_k - count #move left
  int_move_devide_2_no_amari = int_move % 2
  print(abs(param_x_tmp + param_d*int_move_devide_2_no_amari*int_times_nega_posi*-1))

### FIXED CODE ###

param_x, param_k, param_d = map(int, input().split())

param_x_tmp = param_x

if param_x > 0:
  int_times_nega_posi = -1
else:
  int_times_nega_posi =  1
  
if (param_x*int_times_nega_posi*-1) - (param_k*param_d) > 0:
  print((param_x*int_times_nega_posi*-1) - (param_k*param_d))
  
else:
  int_time_before_cross_0 = int((param_x*int_times_nega_posi*-1) / param_d)
  # print(int_time_before_cross_0)
  
  param_x_tmp = param_x + int_time_before_cross_0*param_d*int_times_nega_posi
  # print(param_x_tmp)
  
  int_move = param_k - int_time_before_cross_0 #move left
  int_move_devide_2_no_amari = int_move % 2
  print(abs(param_x_tmp + param_d*int_move_devide_2_no_amari*int_times_nega_posi))
  
  #count = 0
  #while param_x_tmp*param_x > 0:
  #  
  #  param_x_tmp = param_x_tmp + param_d*int_times_nega_posi
  #  
  #  count = count + 1
  #  
  #  if param_k - count == 0:
  #    print(abs(param_x_tmp))
  #
  #if count < param_k:
  #  int_move = param_k - count #move left
  #  int_move_devide_2_no_amari = int_move % 2
  #  print(abs(param_x_tmp + param_d*int_move_devide_2_no_amari*int_times_nega_posi*-1))
### BUGGY CODE ###

MOD = 10**9+7

memo = dict()
memo[0] = 1
def pow3(n):
	if n in memo:
		return memo[n]
	if n%2 == 0:
		tmp = pow3(n//2)
		memo[n] = tmp*tmp%MOD
		return memo[n]
	memo[n] = 3 * pow3(n-1)%MOD
	return memo[n]

def cul(i, p):
	cur = (1<<i)%MOD
	cur *= pow3(p)
	return cur % MOD

def solve(L):
	n = len(L)
	if L == "0":
		print(1)
		return

	num_1 = 0
	pos = []
	for i in range(n):
		if L[i] == "1":
			num_1 += 1
			pos.append(n-i-1)

	ans = (2**num_1)%MOD
	for i, p in enumerate(pos):
		ans += cul(i, p)
		ans %= MOD

	return ans

def main():
	L = input()
	print(solve(L))


if __name__ == '__main__':
	main()

### FIXED CODE ###

MOD = 10**9+7

memo = dict()
memo[0] = 1
def pow3(n):
	if n in memo:
		return memo[n]
	if n%2 == 0:
		tmp = pow3(n//2)
		memo[n] = tmp*tmp%MOD
		return memo[n]
	memo[n] = 3 * pow3(n-1)%MOD
	return memo[n]

def cul(i, p):
	cur = (1<<i)%MOD
	cur *= pow3(p)
	return cur % MOD

def solve(L):
	n = len(L)
	if L == "0":
		return 1
	if not "0" in L:
		return pow3(n)

	num_1 = 0
	pos = []
	for i in range(n):
		if L[i] == "1":
			num_1 += 1
			pos.append(n-i-1)

	ans = (2**num_1)%MOD
	for i, p in enumerate(pos):
		ans += cul(i, p)
		ans %= MOD

	return ans

def main():
	L = input()
	print(solve(L))


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

n, m = map(int, input().split(" "))
r = [""] * m
for c in range(m):
    r[c] = list(map(int, input().split(" ")))
ac = 0
for c in range(n):
    num = c + 1
    for co in range(m):
        if r[co][0] <= num <= r[co][1]:
            pass
        else:
            break
    else:
        ac += 1
print(ac)

### FIXED CODE ###

N, M = map(int, input().split())
L = [0] * M
R = [0] * M
for c in range(M):
    L[c], R[c] = map(int, input().split())

L_max = max(L)
R_min = min(R)

ans = R_min - L_max
ans += 1

if ans < 0:
    print(0)
else:
    print(ans)
### BUGGY CODE ###

import math


def gcd(a, b, c):

    return math.gcd(math.gcd(a, b), c)


k = int(input())
answer = 0
for w_a in range(1, k + 1):
    for w_b in range(1, k + 1):
        for w_c in range(1, k + 1):
            answer += gcd(w_a, w_b, w_c)

print(answer)


### FIXED CODE ###

import math


k = int(input())
answer = 0
for w_a in range(1, k + 1):
    for w_b in range(1, k + 1):
        w = math.gcd(w_a, w_b)
        for w_c in range(1, k + 1):
            answer += math.gcd(w, w_c)

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

#!/usr/bin/env python3

N = int(input())

ans = 0
for i in range(1,N):
    ans += i

print(ans)


### FIXED CODE ###

#!/usr/bin/env python3

N = int(input())

ans = (1+(N-1))*(N-1)//2

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

from collections import Counter
from scipy.misc import comb
N = int(input())
A = [int(x) for x in input().split()]
C = Counter(A)
def banned_count(seq):
    for i in range(N):
        count = 0
        C[A[i]] -= 1
        for j in C.values():
            count += comb(j, 2, exact=True)
        print(count)
        C[A[i]] += 1
banned_count(A)

### FIXED CODE ###

from collections import Counter
from scipy.misc import comb
N = int(input())
A = input().split()
C = Counter(A)
s = sum([comb(j, 2, exact=True) for j in C.values()])
for i in range(N):
    print(s-C[A[i]]+1)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)
from bisect import bisect_right

N, M = mapint()
AB = []
for _ in range(N):
    a, b = mapint()
    AB.append((a, -b))
AB.sort()

days = [0]*M
for a, b in AB:
    a -= 1
    if a>=M:
        continue
    if days[a]==0:
        days[a] = b
    else:
        idx = bisect_right(days[a:], b)
        if a+idx>=M:
            continue
        days[a+idx:] = [b]+days[a+idx:-1]

print(-sum(days[::-1]))

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)
from bisect import bisect_right

N, M = mapint()

from heapq import heappop, heappush
days = [[] for _ in range(M)]
for _ in range(N):
    a, b = mapint()
    if a>M:
        continue
    days[a-1].append(-b)

queue = []

ans = 0
for i in range(M):
    lis = days[i]
    for b in lis:
        heappush(queue, b)
    if queue:
        ans += heappop(queue)

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

class BIT:
    def __init__(self,n):
        self.size = n
        self.tree = [0]*(n+1)

    def add(self,i,x):
        while i <= self.size:
            self.tree[i] += x
            i += i&-i

    def sum(self,i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i&-i
        return s

N,Q = map(int,input().split())
C = list(map(int,input().split()))
LR = [list(map(int,input().split()))+[i] for i in range(Q)]
bit = BIT(N)
#color[i] => 色iが最後に登場したインデックス(1-indexed)
color = [0]*(N+1)

ANS = []
LR.sort(key=lambda x: x[1])
cur = 1
for l,r,i in LR:
    while cur <= r:
        c = C[cur-1]
        if color[c] == 0:
            color[c] = cur
            bit.add(cur,1)
        else:
            bit.add(color[c],-1)
            color[c] = cur
            bit.add(cur,1)
        cur += 1
    ANS.append((bit.sum(r)-bit.sum(l-1),i))
ANS.sort(key=lambda x: x[1])
for a,i in ANS:
    print(a)


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    class BIT:
        def __init__(self,n):
            self.tree = [0]*(n+1)
            self.size = n
        
        def add(self,i,x):
            while i <= self.size:
                self.tree[i] += x
                i += i&-i
        
        def sum(self,i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i&-i
            return s

    N,Q = map(int,input().split())
    bit = BIT(N)
    C = list(map(int,input().split()))
    query = []
    for i in range(Q):
        l,r = map(int,input().split())
        query.append([l,r,i])
    query.sort(key=lambda x: x[1])
    ans = [0]*Q
    #良い玉のindexを1-indexで管理する
    colorMemo = [0]*(N+1)
    cur = 1
    for q in query:
        l,r,j = q
        #良い玉の情報を更新する
        for i in range(cur,r+1):
            c = C[i-1]
            if colorMemo[c]:
                bit.add(colorMemo[c],-1)
            bit.add(i,1)
            colorMemo[c] = i
        cur = r + 1
        ans[j]=bit.sum(r)-bit.sum(l-1)

    print(*ans, sep="\n")
main()
### BUGGY CODE ###

s = input()
ans = 0
for i in range(len(s)-3):
  j = i + 3
  while(j <= len(s)):
    if int(s[i:j+1]) % 2019 == 0:
      ans += 1
      j += 4
    else:
      j += 1
print(ans)

### FIXED CODE ###

s = input()
p = 2019
n = 0
ans = 0
mods = [0]*p
mods[0] = 1
for i, j in enumerate(reversed(s)):
  n += int(j)*pow(10, i, p)
  n %= p
  mods[n] += 1
for i in mods:
  ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

import itertools
n=int(input())
a=(map(int,input().split()))
ans=0
for a,b in itertools.combinations(a,2):
    ans+=(a*b)%(10**9+7)
    ans%=(10**9+7)
print(ans%(10**9+7))


### FIXED CODE ###

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

L, R = map(int, input().split())
l = []
for i in range(R-L):
    for j in range(R-L):
        l.append((L+i)*(L+1+j)%2019)
print(min(l))

### FIXED CODE ###

L, R = map(int, input().split())
l = []
if R - L >= 672:
    print(0)
else:
    for i in range(L,R):
        for j in range(i+1,R+1):
            l.append(i*j%2019)
    print(min(l))
### BUGGY CODE ###

def cmb(n,r,mod):
    p,q=1,1
    if r>n/2:
        r=n-r
    for i in range(r):
        p*=n-i
        q*=i+1
    return (p*pow(q,mod-2,mod))%mod
    
n,a,b=map(int,input().split())
mod=10**9+7
v=pow(2,n,mod)-1
print((v-cmb(n,a,mod)-cmb(n,b,mod))%mod)

### FIXED CODE ###

def cmb(n,r,mod):
    p,q=1,1
    if r>n/2:
        r=n-r
    for i in range(r):
        p*=n-i
        p%=mod
        q*=i+1
        q%=mod
    return (p*pow(q,mod-2,mod))%mod
    
n,a,b=map(int,input().split())
mod=10**9+7
v=pow(2,n,mod)-1
print((v-cmb(n,a,mod)-cmb(n,b,mod))%mod)
### BUGGY CODE ###

def resolve():
    import sys
    import numpy as np

    read = sys.stdin.read
    readline = sys.stdin.readline

    N, K = map(int, readline().split())
    h = np.array(read().split(), np.int32)

    # 貰うDP
    inf = 10 ** 9
    dp = np.full(N + K, inf, np.int32)
    dp[0] = 0

    for i in range(1, N):
        leng = i + 1 if i < K else K + 1
        for j in range(leng):
            # 高速化ののため，min関数ではなくif文を使用
            cal = dp[i - j] + abs(h[i] - h[i - j])
            if dp[i] > cal:
                dp[i] = cal

    print(dp[N - 1])
            

resolve()


### FIXED CODE ###

def resolve():
    import sys
    
    readline = sys.stdin.readline

    N, K = map(int, readline().split())
    h = [int(x) for x in readline().split()]

    inf = float('inf')
    dp = [inf] * N
    dp[0] = 0

    for i in range(1, N):
        leng = i + 1 if i < K else K + 1
        for j in range(leng):
            cal = dp[i - j] + abs(h[i] - h[i - j])
            if dp[i] > cal:
                dp[i] = cal

    print(dp[-1])
            

resolve()
### BUGGY CODE ###

n, k = map(int, input().split())
h = sorted([int(input()) for _ in range(n)])
ans = 999999999999
for x in range(n-k+1):
    ans = min(max(h[x:x+k]) - min(h[x:x+k]), ans)
print(ans)


### FIXED CODE ###

import numpy as np
n, k = map(int, input().split())
h = np.array([int(input()) for _ in range(n)],dtype=int)
h.sort()
print(min([h[x+k-1] - h[x] for x in range(n-k+1)]))
### BUGGY CODE ###

N = input()
l = list(map(int,input().split()))
for i in range(len(l)):
    if not l.count(l[i])== 1:
      print("NO")
      break
    elif i == len(l)-1:
      print("YES")

### FIXED CODE ###

N=input()
l=list(map(int,input().split()))
if len(l)!=len(set(l)):
  print("NO")
else:
  print("YES")
### BUGGY CODE ###

from sys import stdin
N, K = [int(_) for _ in stdin.readline().rstrip().split()] 
H = [int(_) for _ in stdin.readline().rstrip().split()] 
dp = [10**9] * N
dp[0] = 0
for i in range(N-1):
  for j in range(1, min(K+1, N-i)):
    dp[i+j] = min(dp[i] + abs(H[i]-H[i+j]), dp[i+j])
print(dp[N-1])

### FIXED CODE ###

from sys import stdin
N, K = [int(_) for _ in stdin.readline().rstrip().split()] 
H = [int(_) for _ in stdin.readline().rstrip().split()] 
dp = [10**9] * N
dp[0] = 0
for i in range(N-1):
  for j in range(1, min(K+1, N-i)):
    dp[i+j] = min(dp[i] + abs(H[i]-H[i+j]), dp[i+j])
print(dp[N-1])
### BUGGY CODE ###

import fractions
from functools import reduce
import copy

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

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

ans_list = []
for i in range(n):
    tmp_list = copy.copy(a_list)
    if i == 0:
        tmp = gcd(*tmp_list[1:])
    
    elif i == n-1:
        tmp = gcd(*tmp_list[:-1])
    
    else:
        tmp_l = gcd(*tmp_list[0:i])
        tmp_r = gcd(*tmp_list[i+1:])
        tmp = gcd(tmp_l, tmp_r)
    
    ans_list.append(tmp)

print(max(ans_list))


### FIXED CODE ###

from fractions import gcd
import copy

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

ans_list = []
l_list = [0]*(n+1)
r_list = [0]*(n+1)

for i in range(n):
    l_list[i+1] = gcd(l_list[i], a_list[i])
    r_list[n-i-1] = gcd(r_list[n-i], a_list[n-i-1])

ans_list = []
for j in range(n):
    ans_list.append(gcd(l_list[j], r_list[j+1]))

#print(ans_list)

print(max(ans_list))
### BUGGY CODE ###

from collections import Counter
def main():
    n = int(input())
    a = Counter(map(int, input().split()))
    dp = [[[''] * (310) for _ in range(310)] for _ in range(310)]
    def exp(i,j,k):
        if i + j + k == 0:
            return 0
        if dp[i][j][k]:
            return dp[i][j][k]
        ans = n
        if i > 0:
            ans += i * exp(i-1,j,k)
        if j > 0:
            ans += j * exp(i+1,j-1,k)
        if k > 0:
            ans += k * exp(i,j+1,k-1)
        ans /= (i+j+k)
        dp[i][j][k] = ans
        return ans

    ans = exp(a[1],a[2],a[3])
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import Counter
import sys
input = sys.stdin.buffer.readline

def main():
    n = int(input())
    a = Counter(map(int, input().split()))
    dp = [[[.0] * (n+1) for _ in range(n+1)] for _ in range(n+1)]
    for k in range(a[3]+1):
        for j in range(a[2]+a[3]-k+1):
            for i in range(n-j-k+1):
                if i + j + k == 0:
                    continue
                tmp = n
                if i > 0:
                    tmp += i * dp[i-1][j][k]
                if j > 0:
                    tmp += j * dp[i+1][j-1][k]
                if k > 0:
                    tmp += k * dp[i][j+1][k-1]
                dp[i][j][k] = tmp / (i+j+k)
    print(dp[a[1]][a[2]][a[3]])

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

r,g,b,n = map(int,input().split())

ans = 0

num = [r,g,b]
#print(num)
num.sort()
#print(num[0],num[1])
#exit()

for i in range(n+1):
    if i * num[2] > n:
        break
    for j in range(n+1):
        #if i + j >= n:
            #ans = ans + 1
        #    break
        if (n - i*num[2] - j*num[1]) < 0:
            break
        if (n - i*num[2] - j*num[1]) % num[0] == 0:
            ans = ans + 1

print(ans)

### FIXED CODE ###

r,g,b,n = map(int,input().split())

ans = 0

num = [r,g,b]
#print(num)
num.sort()
#print(num[0],num[1])
#exit()

for i in range(n+1):
    if i * num[2] > n:
        break
    for j in range(n+1):
        #if i + j >= n:
            #ans = ans + 1
        #    break
        if (n - i*num[2] - j*num[1]) < 0:
            break
        if (n - i*num[2] - j*num[1]) % num[0] == 0:
            ans = ans + 1

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

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

idou = set()
for i in range(0, K):
    L, R = map(int, input().split())
    idou = idou | set(range(L, R + 1))

idou = list(idou)

moves = [0] * N
moves[0] = 1
for i in range(0, N):
    for j in range(0, len(idou)):
        if i + idou[j] < N:
            moves[i + idou[j]] += moves[i]

print(moves[N - 1] % 998244353)


### FIXED CODE ###

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

L = [0] * K
R = [0] * K
for i in range(0, K):
    L[i], R[i] = map(int, input().split())

moves = [0] * N
moves[0] = 1

rui_wa = [0] * N
rui_wa[0] = 1

for i in range(1, N):
    for j in range(0, K):
        l = max(i - L[j], 0)
        r = max(i - R[j], 0)
        if i - L[j] < 0:
            continue

        moves[i] += (rui_wa[l] - rui_wa[r - 1]) % 998244353

    rui_wa[i] = (moves[i] + rui_wa[i - 1])  % 998244353



print(moves[N - 1] % 998244353)
### BUGGY CODE ###

# A

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

Acum = [0] + A
ls = set()
ls.add(0)
for i in range(1, N+1):
    Acum[i] += Acum[i-1]
    ls.add(Acum[i])

lst = []
for n in ls:
    num = Acum.count(n)
    if num > 1:
        lst.append(num * (num - 1) / 2)

if lst:
    print(int(sum(lst)))
else:
    print(0)

### FIXED CODE ###

# A

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

Acum = [0] + A
dic = {0: 1}
for i in range(1, N + 1):
    Acum[i] += Acum[i - 1]
    if Acum[i] in dic.keys():
        dic[Acum[i]] += 1
    else:
        dic[Acum[i]] = 1
ans = 0
for v in dic.values():
    if v > 1:
        ans += int(v * (v - 1) / 2)

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

import sys
input = sys.stdin.readline
def main():
    n,m=map(int,input().split())
    p = [int(i)-1 for i in input().split() ]
    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n
    
        def find(self, x):
            if self.parents[x] < 0:
                return x
            else:
                self.parents[x] = self.find(self.parents[x])
                return self.parents[x]
    
        def union(self, x, y):
            x = self.find(x)
            y = self.find(y)
    
            if x == y:
                return
    
            if self.parents[x] > self.parents[y]:
                x, y = y, x
    
            self.parents[x] += self.parents[y]
            self.parents[y] = x
    
        def size(self, x):
            return -self.parents[self.find(x)]
        
        def same(self, x, y):
            return self.find(x) == self.find(y)
    
        def members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]
    
        def roots(self):
            return [i for i, x in enumerate(self.parents) if x < 0]
    
        def group_count(self):
            return len(self.roots())
    
        def all_group_members(self):
            return {r: self.members(r) for r in self.roots()}
    
          
    uf = UnionFind(n)
    for i in range(m):
        x,y = map(int,input().split())
        uf.union(x-1,y-1)
    
    ans=0
    groups = uf.all_group_members().values()
    for cand in groups:
        ans+=len(set(cand) & set(p[i] for i in cand) )
    print(ans)
    
main()

### FIXED CODE ###

n,m=map(int,input().split())
p = [int(i)-1 for i in input().split() ]


tree=[[] for _ in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

from collections import deque

groups=[]
been=[0]*n
for i in range(n):
    if been[i]==0:
        group=[i]
        been[i]=1
        q = deque([(i,togo) for togo in tree[i]]) 
        while q:
            parent,x = q.popleft()
            if been[x]==1:
                continue
            been[x]=1
            group.append(x)
            for y in tree[x]:
                if y == parent:#親ノードを飛ばし
                    continue
                q.append((x,y))#子ノードを追加
        groups.append(group)

ans=0
for group in groups:
    ans+= len( set(group) & set(p[g] for g in group) )

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

INF = 1000000000

def solve(s,g,E,n):
  D = [INF for i in range(n)]
  D[s] = 0
  V = [(0,s)]
  U = [0 for i in range(n)]
  while V:
    v = V.pop(0)
    U[v[1]] = 1
    for e in E[v[1]]:
      if U[e[0]] == 0 and D[v[1]] + e[1] < D[e[0]]:
        D[e[0]] = D[v[1]] + e[1]
        V.append((D[e[0]],e[0]))
        V.sort()
  if D[g] >= INF:
    print(-1)
  else:
    print(D[g])

while True:
  try:
    n,k = list(map(int,input().split()))
    if n == 0 and k == 0:
      break
    E = [[] for i in range(n)]
    for i in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        solve(lst[1] - 1, lst[2] - 1, E, n)
      elif lst[0] == 1:
        E[lst[1] - 1].append([lst[2] - 1, lst[3]])
        E[lst[2] - 1].append([lst[1] - 1, lst[3]])
  except EOFError:
    break


### FIXED CODE ###

from heapq import heappush,heappop

def dij(s,g,E):
  h = []
  U = []
  heappush(h,(0,s))
  while h:
    v = heappop(h)
    if v[1] == g:
      if v[0] >= INF:print(-1)
      else:print(v[0])
      break
    U.append(v[1])
    for e in E[v[1]]:
      if not e[0] in U:
        heappush(h,(v[0] + e[1],e[0]))
  else:print(-1)
INF = 100000000
while True:
  try:
    n,k = map(int,input().split())
    if n == 0 and k == 0: break
    E = [[] for i in range(n)]
    for _ in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        dij(lst[1] - 1, lst[2] - 1, E)
      else:
        E[lst[1] - 1].append([lst[2] - 1, lst[3]])
        E[lst[2] - 1].append([lst[1] - 1, lst[3]])

  except EOFError:
    break
### BUGGY CODE ###

n = int(input())

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

x = 1

for i in range(n):
    x = x * a[i]
    
if x <= 10 ** 18:
    print(x)
else:
    print(-1)


### FIXED CODE ###

n = int(input())

a = sorted(list(map(int, input().split())))

x = 1

for i in range(n):
    x = x * a[i]
    if x == 0:
        break
    elif x > 10 ** 18:
        x = -1
        break

print(x)
### BUGGY CODE ###

s = input()[::-1]
 
sum_of_digits = 0
cnts = [0]*2019
cnts[0] = 1
 
d = 1
 
for c in s:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10
    cnts[sum_of_digits] += 1
 
ans = 0
for cnt in cnts:
    ans += cnt * (cnt - 1) // 2
 
print(ans)

### FIXED CODE ###

s = input()[::-1]

sum_of_digits = 0
cnts = [0]*2019
cnts[0] = 1

d = 1

for c in s:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10
    d %= 2019
    cnts[sum_of_digits] += 1

ans = 0
for cnt in cnts:
    ans += cnt * (cnt - 1) // 2

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

N = int(input())
A = [int(input()) for _ in range(N)]
for i in range(N):
    print(max(A[:i]+A[i+1:]))


### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
m = max(A)
max_num = 0
for i in range(N):
    if A[i] == m:
        max_num += 1
        if max_num >1:
            print(m)
        else:
            print(max(A[:i]+A[i+1:]))
    else:
        print(m)
### BUGGY CODE ###

import itertools

n = int(input())
L = list(map(int, input().split()))
M = []

for v in itertools.combinations(L, 3):
    M.append(list(v))

cnt = 0

for v in M:
    if v[0] < v[1]+v[2] and v[1] < v[0]+v[2] and v[2] < v[0]+v[1]:
        cnt += 1
        
print(cnt)


### FIXED CODE ###

from bisect import bisect_left
n = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0

for i in range(n):
    for j in range(i+1, n):
        ans += bisect_left(L, L[i]+L[j])-j-1
print(ans)
### BUGGY CODE ###

roop = input()
for k in range(roop):
    str1 = raw_input()
    str2 = raw_input()
    len1 = len(str1) + 1
    len2 = len(str2) + 1
    ans = [None] * (len1)
    for i in xrange(len1):
        ans[i] = [None] * (len2)
    for i in range(len1):
        ans[i][0] = 0
    for j in range(len2):
        ans[0][j] = 0
    for i in range (1, len1):
        for j in range(1, len2):
            if(str1[i - 1] == str2[j - 1]):
                ans[i][j] = ans[i -1][j - 1] + 1
            else:
                ans[i][j] = max(ans[i - 1][j], ans[i][j - 1])
    print ans[len1 - 1][len2 - 1]

### FIXED CODE ###

def LCS():
    str1 = raw_input()
    str2 = raw_input()
    
    after = [0] * (len(str2) + 1)
    
    for i in xrange(1, len(str1) + 1):
        before = after + []
        for j in xrange(1, len(str2) + 1):
             if str1[i - 1] == str2[j - 1]:
                 after[j] = before[j - 1] + 1
             elif after[j - 1] > before[j]: #this is equal to 'max(after[j - 1], before[j])'
                 after[j] = after[j - 1]
    return after[j]

n = input()
for k in xrange(n):
    print LCS()