Harryxun/stf_run huggingface dataset:
#!/usr/bin/env python3
#E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def comb(n, r):
    return fact[n]*pow(fact[n-r], mod-2, mod)*pow(fact[r], mod-2, mod) % mod
n = I()
ab = [LI() for _ in range(n)]
ans = pow(2, n, mod) - 1
fact = [1]*(n+1)
for i in range(1, n+1):
    fact[i] = i * fact[i-1]
    fact[i] %= mod
a_zero = 0
b_zero = 0
AB = []
for a, b in ab:
    if a == 0 and b == 0:
        ans -= pow(2, n-1, mod)
        ans %= mod
        n -= 1
    elif a == 0:
        a_zero += 1
    elif b == 0:
        b_zero += 1
    else:
        AB.append([a, b])
x = [a / b for a, b in AB]
y = [- b / a for a, b in AB]

j = 0
if a_zero:
    while j + 1 < b_zero:
        ans -= comb(b_zero, j + 2) * pow(2, n - (b_zero - (j+2)) - (j+2), mod)
        ans %= mod
        j += 1
    n -= b_zero
lst = []
z = defaultdict(lambda : 0)
for i,j in enumerate(x):
    if z[j]:
        lst.append(z[j]+1)
    z[y[i]] += 1
for i in lst:
    j = 0
    while j + 1 < i:
        ans -= comb(i, j+2) * pow(2, n - (i-(j+2)) - (j+2), mod)
        ans %= mod
        j += 1
    n -= i
print(ans)




### FIXED CODE ###

#!/usr/bin/env python3
#E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def comb(n, r):
    return fact[n]*pow(fact[n-r], mod-2, mod)*pow(fact[r], mod-2, mod) % mod
n = I()
ab = [LI() for _ in range(n)]

fact = [1]*(n+1)
for i in range(1, n+1):
    fact[i] = i * fact[i-1]
    fact[i] %= mod

x = defaultdict(lambda : 0)
y = defaultdict(lambda : 0)
z = defaultdict(lambda : 0)
tmp = 0
for a, b in ab:
    if a == 0 and b == 0:
        tmp += 1
    elif a == 0:
        x[0] += 1
        z[0] = 1
    elif b == 0:
        y[0] += 1
        z[0] = 1
    else:
        if a * b > 0:
            g = math.gcd(a, b)
            a //= g
            b //= g
            x[(abs(a), abs(b))] += 1
            z[(abs(a), abs(b))] = 1
        else:
            g = math.gcd(a, b)
            a //= g
            b //= g
            y[(abs(b), abs(a))] += 1
            z[(abs(b), abs(a))] = 1

ans = 1
for i in z.keys():
    ans *= (2**x[i] + 2**y[i] - 1)
    ans %= mod
ans -= 1
ans += tmp
ans %= mod
print(ans)
def inN():
    return int(input())
def inL():
    return list(map(int,input().split()))
n = inN()
a = inL()
if 0 in a:
    print(0)
    exit()

sum = 1
for i in range(n):
    sum *= a[i]
    if sum <= pow(10,18):
        print(-1)
        exit()
print(sum)

### FIXED CODE ###

def inN():
    return int(input())
def inL():
    return list(map(int,input().split()))

a,b = inL()
print(a*b)
from functools import*
@lru_cache(None)
def solve(n,m):
  if not n:return 1
  n%=m
  return-~solve(n,bin(n).count('1'))
n=int(input())
s=input()
a=int(s,2)
*x,=map(int,s)
h=sum(x)
a,b=a%(h-1),a%(h+1)
for i in range(n):
  if x[i]:
    x[i]=0
    t=(a-pow(2,~i+n,h-1))%(h-1)
  else:
    x[i]=1
    t=(b+pow(2,~i+n,h+1))%(h+1)
  r=solve(t,bin(t).count('1'))
  x[i]^=1
  print(r)

### FIXED CODE ###

from functools import*
@lru_cache(None)
def solve(n,m):
  if not n:return 1
  n%=m
  return-~solve(n,bin(n).count('1'))
n=int(input())
s=input()
a=int(s,2)
*x,=map(int,s)
h=sum(x)
try:a,b=a%(h-1),a%(h+1)
except:b=a%(h+1)
for i in range(n):
  if x[i]:
    if not h-1:
      print(0)
      continue
    x[i]=0
    t=(a-pow(2,~i+n,h-1))%(h-1)
  else:
    x[i]=1
    t=(b+pow(2,~i+n,h+1))%(h+1)
  r=solve(t,bin(t).count('1'))
  x[i]^=1
  print(r)
# -*- coding: utf-8 -*-

N,W = map(int, input().split())
wN = []
vN = []
for i in range(N):
    w,v = map(int, input().split())
    wN.append(w)
    vN.append(v)

dp = [[0] * (3*(N-1)+100) for i in range(N+1)]

# 答えが明らかな範囲はDPに含めない
if W < wN[0]:
    print(0)
    exit()
elif W >= sum(wN):
    print(sum(vN))
    exit()

# wNの範囲はかなり限定されているので、オフセットを用意
# (-1するのは0地点を残すため)
offset = wN[0]-1
W -= offset

for i in range(N):
    for j in range(offset, (3*(N-1)+100) + offset):

        if wN[i] <= j:
            # max(0,～)で0未満を探しに行くのを避ける
            dp[i+1][j-offset] = max(dp[i][max(0,j-wN[i]-offset)] + vN[i], dp[i][j-offset])
        else:
            dp[i+1][j-offset] = dp[i][j-offset]

print(dp[N][W])

### FIXED CODE ###

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

"""
・メモ化再帰
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

from collections import defaultdict

N, W = map(int, input().split())
wN = [0] * N
vN = [0] * N
for i in range(N):
    wN[i], vN[i] = map(int, input().split())

# memo[i][j]: i番目以降の品物から重さの和がj以下なるように選んだときの価値の和の最大値
memo = [defaultdict(lambda: -1) for i in range(N+1)]

def dfs(cur, wei):
    # 既に調べた場所はそのまま返却
    if memo[cur][wei] != -1:
        return memo[cur][wei]
    # 品物を最後まで見た
    if cur == N:
        res = 0
    # まだ余力があるから両方試す
    elif wei >= wN[cur]:
        res = max(dfs(cur+1, wei-wN[cur]) + vN[cur], dfs(cur+1, wei))
    # もうこの回の荷物は入らない
    else:
        res = dfs(cur+1, wei)
    # ここまでのベストな値をメモに記録してから返却
    memo[cur][wei] = res
    return res
# 0番目以降で容量W以下の場合の結果を表示
print(dfs(0, W))
import math
A, B = [int(x) for x in input().split()]


gap = B - A


if gap == 1:
  print(1)
elif gap > 1:
  print(int(mathy.ceil(B / A)))
else:
  print(0)

### FIXED CODE ###

A, B = [int(x) for x in input().split()]

ans = 0
x = 1
while x < B:
  x = A * ans - ans + 1
  ans += 1
ans = ans-1
if ans < 0:
  ans = 0
print(ans)
# coding=utf-8
# Date: 2020-04-07 00:38

get = lambda: int(raw_input().strip())
getl = lambda: raw_input().strip()
gets = lambda: map(int, raw_input().strip().split())
getss = lambda n: [gets() for _ in xrange(n)]

# fi = open('sample4.in', 'r')
# raw_input = fi.readline

n = get()
G = [set() for i in xrange(n + 1)]
for i in xrange(n - 1):
    i, j = gets()
    G[i].add(j)
    G[j].add(i)
mod = 10**9 + 7


def dfs(i):
    G[i], A = None, G[i]
    black, white = 1, 1
    for j in A:
        G[j].remove(i)
        b, w = dfs(j)
        black = black * w % mod
        white = white * (b + w) % mod
    return [black, white]
print sum(dfs(1))


### FIXED CODE ###

# coding=utf-8
# Date: 2020-04-07 00:38

import sys
sys.setrecursionlimit(10**6)

get = lambda: int(raw_input().strip())
getl = lambda: raw_input().strip()
gets = lambda: map(int, raw_input().strip().split())
getss = lambda n: [gets() for _ in xrange(n)]

n = get()
G = [[] for i in xrange(n + 1)]
for i in xrange(n - 1):
    i, j = gets()
    G[i].append(j)
    G[j].append(i)
mod = 10**9 + 7


def dfs(i, pre=0):
    black, white = 1, 1
    for j in G[i]:
        if j == pre: continue
        b, w = dfs(j, i)
        black = black * w % mod
        white = white * (b + w) % mod
    return [black, white]
print sum(dfs(1)) % mod
N,a,b = map(int,[input()  for _ in range(3)])
total= 0
ans = 0
for i in range(1,N+1):
    st_i = str(i)
    for j in range(4):
        try:
            total += int(st_i[j])
        except:
            pass


    if a <= total <= b:
        ans += i
    total = 0

print(ans)

### FIXED CODE ###

N,a,b = map(int,input().split(" "))
total= 0
ans = 0
for i in range(1,N+1):
    st_i = str(i)
    for j in range(4):
        try:
            total += int(st_i[j])
        except:
            pass


    if a <= total <= b:
        ans += i
    total = 0

print(ans)
n=int(input())

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

ki=[0]*100001
gu=[0]*100001

for i in range(n):
    if i%2==0:
        ki[l[i]]+=1
    else:
        gu[l[i]]+=1
km1=[max(ki),ki.index(max(ki))]
km2=[sorted(ki)[-2],ki.index(sorted(ki)[-2])]
gm1=[max(gu),gu.index(max(gu))]
gm2=[sorted(gu)[-2],gu.index(sorted(gu)[-2])]

if km1[1]!=gm1[1]:
    print(n-km1[0]-gm[0])
else:
    if km1[1]-km2[1]>=gm1[1]-gm2[1]:
        print(n-km1[0]-gm2[0])
    else:
        print(n-gm1[0]-km2[0])



### FIXED CODE ###

n=int(input())

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

ki=[0]*100001
gu=[0]*100001

for i in range(n):
    if i%2==0:
        ki[l[i]]+=1
    else:
        gu[l[i]]+=1
km1=[max(ki),ki.index(max(ki))]
km2=[sorted(ki)[-2],ki.index(sorted(ki)[-2])]
gm1=[max(gu),gu.index(max(gu))]
gm2=[sorted(gu)[-2],gu.index(sorted(gu)[-2])]

if km1[1]!=gm1[1]:
    print(n-km1[0]-gm1[0])
else:
    if km1[0]-km2[0]>=gm1[0]-gm2[0]:
        print(n-km1[0]-gm2[0])
    else:
        print(n-gm1[0]-km2[0])
N,M = (int(i) for i in input().split())
K = []
for i in range(M):
    J = [int(i) for i in input().split()]
    J.sort()
    K.append(J)

#1以外の頂点リストを作成
vertex = []
for i in range(N-1):
    vertex.append(i+2)
#順列作成
X = list(itertools.permutations(vertex))

#各値ごとに有無をチェック
ans = 0
for i in X:
    start = 1
    localcount = 0
    for j in i:
        tmp = [start,j]
        tmp.sort()
        if tmp in K:            
            localcount += 1   
        start = j
            
    if localcount == N-1:
        ans += 1

print(ans)  

### FIXED CODE ###

import itertools
N,M = (int(i) for i in input().split())
K = []
for i in range(M):
    J = [int(i) for i in input().split()]
    J.sort()
    K.append(J)

#1以外の頂点リストを作成
vertex = []
for i in range(N-1):
    vertex.append(i+2)
#順列作成
X = list(itertools.permutations(vertex))

#各値ごとに有無をチェック
ans = 0
for i in X:
    start = 1
    localcount = 0
    for j in i:
        tmp = [start,j]
        tmp.sort()
        if tmp in K:            
            localcount += 1   
        start = j
            
    if localcount == N-1:
        ans += 1

print(ans)
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))

from collections import Counter

n = ii()
A = iil()

di = Counter(A)
A.sort()

ans = 0
l = []
for item in A:
    if di[item] > 1:
        if l[-1] != item:
            l.append(item)
        continue
    flag = True
    for i in l:
        if item%i == 0:
            flag = False
            break
    if flag:
        l.append(item)
        ans += 1
print(ans)


### FIXED CODE ###

def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))

from collections import Counter

n = ii()
A = iil()
di = Counter(A)
A.sort()

ans = 0
l = set()
for item in A:
    if di[item] > 1:
        if item not in l:
            for i in range(1,1000000//item+1):
                l.add(item*i)
        continue
    if item not in l:
        for i in range(1,1000000//item+1):
            l.add(item*i)
        ans += 1
print(ans)
s = input()
n = len(s) // 2
p = n
j = -1

for i in range(n):
    if n[i] == n[j]:
        p -= 1
    j -= 1

print(p)

### FIXED CODE ###

s = input()
n = len(s) // 2
p = n
j = -1

for i in range(n):
    if s[i] == s[j]:
        p -= 1
    j -= 1

print(p)
a,b,c=map(int,input().split())
print(max(0,c-(a-b))

### FIXED CODE ###

a,b,c=map(int, input().split())
print(max(0, c - (a-b)))
from heapq import *
input = sys.stdin.readline
n,Q = list(map(int, input().split()))
Y=[]
for j in range(n):
    a=list(map(int, input().split()))
    Y.append([a[0]-a[2],a[1]-a[2],a[2]])
q = [int(input()) for i in range(Q)]
Y.sort()
X=[]
p=0
for d in q:
    while p<n and Y[p][0]<=d:
        heappush(X,(Y[p][2],Y[p][1]))
        p+=1
    while X and X[0][1] <= d:
        heappop(X)
    if X:
        print(X[0][0])
    else:
        print(-1)

### FIXED CODE ###

import sys
from heapq import *
input = sys.stdin.readline

n,Q = [int(i) for i in input().split()]

stx=[[0]*3 for _ in range(n)]
for j in range(n):
    a = [int(i) for i in input().split()]
    stx[j]=[a[0]-a[2],a[1]-a[2],a[2]]
q = [int(input()) for i in range(Q)]
stx.sort()

xt=[]
pt=0
for d in q:
    while pt < n and stx[pt][0] <= d:
        heappush(xt,(stx[pt][2],stx[pt][1]))
        pt+=1
    while xt and xt[0][1] <= d:
        heappop(xt)
    if xt:
        print(xt[0][0])
    else:
        print(-1)
s=input()
s[5] = " "
s[13] = " "
print(s)

### FIXED CODE ###

s=input().split(",")
print(s[0],s[1],s[2])
k,n=map(int,input().split())
houses=list(map(int,input().split()))
houses.sort()
maxx=-float('INF')
for i in range(n-1):
    if houses[i+1]-houses[i]>maxx:
        maxx=houses[i+1]-houses[i]

maxx=max([maxx,k-(houses[-1]-houses[0])])
print(maxx)


### FIXED CODE ###

s=input()

if s[2]==s[3]:
  if s[4]==s[5]:
    print("Yes")
  else:
    print('No')
else:
  print('No')
print "Yes" if len(set(list(raw_input())) ==2  else "No"

### FIXED CODE ###

print "Yes" if len(set(list(raw_input()))) ==2  else "No"
n = int(input())
a = list(map(int, input().split()))
table = [0] * (10**9 + 1)
for i in range(n):
  table[a[i]] += 1
x = 0
y = 0
for i in range(10**9, 0, -1):
  if table[i] >= 4:
    if x == 0:
      x = i
      y = i
    else:
      y = i
    break
  elif table[i] >= 2:
    if x == 0:
      x = i
    else:
      y = i
      break
print(x*y)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
used = [0] * n
a.sort(reverse=True)
x = 0
y = 0
for i in range(1,n):
    if a[i - 1] == a[i] and used[i-1] == 0 and used[i] == 0:
        if x == 0:
            x = a[i]
            used[i] = 1
            used[i-1] = 1
        elif y == 0:
            y = a[i]
            used[i] = 1
            used[i-1] = 1
            break
print(x*y)
X = int(input())
Y = int(input())
Z = int(input())
T = X
X = Y
Y = T
print(X,Y,Z)
T1 = X
X = Z
Z = T1
print(X,Y,Z)

### FIXED CODE ###

a,b,c = map(int, input().split())
print(c,a,b)
N = int(input())
MOD = 10**9+7
E = {}
for i in range(0,N+1):
    E[i] = []
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    E[a].append(b)
    E[b].append(a)

dp = [ [0 for i in range(2)] for j in range(1000100)]

def dfs(c,p):
    dp[c][0],dp[c][1] = 1,1
    for to in E[c]:
        if to != p:
            dfs(to,c)
            dp[c][0] *= dp[to][0] + dp[to][1]
            dp[c][1] *= dp[to][0]
            dp[c][0] %= MOD
            dp[c][1] %= MOD

dfs(0,-1)

ans = (dp[0][0] + dp[0][1]) % MOD
print(ans)


### FIXED CODE ###

from heapq import heappush, heappop
import collections
import math
import heapq
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
inf = float("inf")


def main():
    N = int(input())
    E = {}
    for i in range(0, N+1):
        E[i] = []
    for i in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        E[a].append(b)
        E[b].append(a)

    dp = [[0 for i in range(2)] for j in range(100100)]

    def dfs(c, p):
        dp[c][0], dp[c][1] = 1, 1
        for to in E[c]:
            if to != p:
                dfs(to, c)
                dp[c][0] *= dp[to][0] + dp[to][1]
                dp[c][1] *= dp[to][0]

    dfs(0, -1)

    ans = (dp[0][0] + dp[0][1]) % MOD
    print(ans)


if __name__ == '__main__':
    main()
import math

n = int(input())
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())

L = [n,0,0,0,0]
num = 0
while True:
  if L[0] > a:
    L[0] -= a
    a_ = a
  else:
    a_ = L[0]
    L[0] = 0
  if L[1] > b:
    L[1] -= b
    b_ = b
  else:
    b_ = L[1]
    L[1] = 0
  if L[2] > c:
    L[2] -= c
    c_ = c
  else:
    c_ = L[2]
    L[2] = 0
  if L[3] > d:
    L[3] -= d
    d_ = d
  else:
    d_ = L[3]
    L[3] = 0
  if L[4] > e:
    L[e] -= e
    e_ = e
  else:
    e_ = L[4]
    L[4] = 0
  L[1] += a_
  L[2] += b_
  L[3] += c_
  L[4] += d_
  num += 1
  if sum(L) == 0:
    break
print(num)

### FIXED CODE ###

import math

n = int(input())
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())

min_ = min([a,b,c,d,e])
num = math.ceil(n/min_) + 4
print(num)
import math
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

A,B,T = list(map(float,input().split()))

num = ((T+0.5)//A )*B

print(int(num))

### FIXED CODE ###

import math
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

A,B,T = list(map(float,input().split()))

num = ((T+0.5)//A )*B

print(int(num))
n = int (input())
ln = []
ln2 = []
for _ in range(n):
    ln.append( int (input()))

C = collections.Counter(ln)
 
ans = 0
for v in C.items():
    if (v%2 != 0):
        ans += 1

print(ans)

### FIXED CODE ###

import collections
n = int (input())
ln = []
ln2 = []
for _ in range(n):
    ln.append( int (input()))

C = collections.Counter(ln)
 
ans = 0
for k, v in C.items():
    if (v%2 != 0):
        ans += 1

print(ans)
m,n=input().split()
while n>0:
  m=m-int(input())
  n=n-1
print(n)

### FIXED CODE ###

m,n=map(int,input().split())
a=list(map(int,input().split()))
while n>0:
  m= m-a[n-1]
  n=n-1
if m>=0:
  print(m)
else:
  print(-1)
N,X=map(int,input().split())
L=list(map(int,input().split()))
ans=0
tmp=0
for i in range(N+1):
    if tmp>X:
        break
    tmp+=L[i]
    ans+=1
print(ans)

### FIXED CODE ###

N,X=map(int,input().split())
L=[0]+list(map(int,input().split()))
ans=0
tmp=0
for i in range(N+1):
    tmp+=L[i]
    if tmp>X:
        break
    else:
        ans+=1
print(ans)
n, m = map(int, input().split())
    a = []
    b = []
    ans = 0

    for _ in range(n):
        s = list(map(int, input().split()))
        a.append(s[0])
        b.append(s[1])

    lv = [a[i] * b[i] for i in range(len(a))]
    li = sorted(zip(lv, a, b), reverse=True)

    for i in range(m):
        for _ in range(len(li)):
            lab = li.pop(0)
            if lab[1] <= m - i:
                ans += lab[2]
                break

    print(ans)



### FIXED CODE ###

from heapq import heappop, heappush


def p_d():
    n, m = map(int, input().split())
    ab = [tuple(map(int, input().split())) for _ in range(n)]

    ab.sort()
    ans = 0
    j = 0
    H = []

    for i in range(1, m + 1):
        while j < n and ab[j][0] <= i:
            heappush(H, -ab[j][1])
            j += 1

        if H:
            ans -= heappop(H)

    print(ans)


if __name__ == '__main__':
    p_d()
from collections import deque
s = deque(x for x in input())
s.append(0)
k = 0
l = [s[0]]
while True:
  if s[0] == 0:
    break
  elif l[k] == s[0]:
    l.append(s.popleft()+s.popleft())
  else:
    l.append(s.popleft())
  k += 1
print(k)

### FIXED CODE ###

from collections import deque
s = deque(x for x in input())
s.append('END')
k = 0
l = [s.popleft()]
while True:
  if s[0] == 'END':
    break
  elif l[k] == s[0]:
    if s[1] == 'END':
      break
    else:
      l.append(s.popleft()+s.popleft())
  else:
    l.append(s.popleft())
  k += 1
print(len(l))
a=input()
b=int(input())
c=0
if a[0]!="1":
  print(a[0])
if a[0]=="1":
  for i in range(len(a)-1):
    if a[i]=="1" and a[i+1]=="1":
      c=c+1
    else:
      break
  if c>b:
    print(1)
  else:
    print(a[c+1])


### FIXED CODE ###

a=input()
b=int(input())
c=1
if a[0]!="1":
  print(a[0])
if a[0]=="1":
  for i in range(len(a)-1):
    if a[i]=="1" and a[i+1]=="1":
      c=c+1
    else:
      break
  if c>=b:
    print(1)
  else:
    print(a[c])
import re

def solve():
  S = input()
  parts = re.split(r'[^ACGT]', S)
  return max(*map(lambda s: len(s), parts))

print(solve())


### FIXED CODE ###

import re

def solve():
  S = input()
  parts = re.split(r'[^ACGT]', S)
  return max(list(map(lambda s: len(s), parts)))

print(solve())
A,B,C,D=map(int,list(input())

if A+B+C+D==7:
    print('{}+{}+{}+{}=7'.format(A,B,C,D))
elif A-B+C+D==7:
    print('{}-{}+{}+{}=7'.format(A,B,C,D))
elif A+B-C+D==7:
    print('{}+{}-{}+{}=7'.format(A,B,C,D))
elif A+B+C-D==7:
    print('{}+{}+{}-{}=7'.format(A,B,C,D))
elif A-B-C+D==7:
    print('{}-{}-{}+{}=7'.format(A,B,C,D))
elif A+B-C-D==7:
    print('{}+{}-{}-{}=7'.format(A,B,C,D))
elif A-B+C-D==7:
    print('{}-{}+{}-{}=7'.format(A,B,C,D))
elif A-B-C-D==7:
    print('{}-{}-{}-{}=7'.format(A,B,C,D))


### FIXED CODE ###

A,B,C,D=map(int,list(input()))

if A+B+C+D==7:
    print('{}+{}+{}+{}=7'.format(A,B,C,D))
elif A-B+C+D==7:
    print('{}-{}+{}+{}=7'.format(A,B,C,D))
elif A+B-C+D==7:
    print('{}+{}-{}+{}=7'.format(A,B,C,D))
elif A+B+C-D==7:
    print('{}+{}+{}-{}=7'.format(A,B,C,D))
elif A-B-C+D==7:
    print('{}-{}-{}+{}=7'.format(A,B,C,D))
elif A+B-C-D==7:
    print('{}+{}-{}-{}=7'.format(A,B,C,D))
elif A-B+C-D==7:
    print('{}-{}+{}-{}=7'.format(A,B,C,D))
elif A-B-C-D==7:
    print('{}-{}-{}-{}=7'.format(A,B,C,D))
solve():
    seq1 = raw_input()
    seq2 = raw_input()
 
    x, y = len(seq1), len(seq2)
    a1 = [0 for i in range(y+1)]
    for i in range(x):
        e1 = seq1[i]
        a2 = a1+[]
        for j in range(y):
            if e1 == seq2[j]:
                a1[j+1] = a2[j] + 1
            elif a1[j+1] < a1[j]:
                a1[j+1] = a1[j]
    return a1[-1]
 
n = input()
for i2 in range(n):
    print solve()

### FIXED CODE ###

def solve():
    seq1 = raw_input()
    seq2 = raw_input()
 
    x, y = len(seq1), len(seq2)
    a1 = [0 for i in range(y+1)]
    for i in range(x):
        e1 = seq1[i]
        a2 = a1+[]
        for j in range(y):
            if e1 == seq2[j]:
                a1[j+1] = a2[j] + 1
            elif a1[j+1] < a1[j]:
                a1[j+1] = a1[j]
    return a1[-1]
 
n = input()
for i2 in range(n):
    print solve()
*s, = map(int, list(input()))
k = int(input())

while s[0] == 1 and k > 0:
    k -= 1
    s = s[1:]
print(s[0])

### FIXED CODE ###

s = list(map(int, list(input())))
k = int(input())

i = 0
while s[i] == 1 and k != 1:
    k -= 1
    i += 1
print(s[i])
w, h, n = map(int, input().split())
nums_list=[list(map(int, input().split())) for i in range(n)]
minX = 0
maxX = w
minY = 0
maxY = h
for nums in nums_list:
	x, y, a = map(int, nums)
	if a == 1:
		minX = minX if (minX > x) else x
	elif a == 2:
		maxX = maxX if (maxX < x) else x
	elif a == 3:
		minY = minY if (minY > y) else y
	elif a == 4:
		maxY = maxY if (maxY < y) else y
width = maxX-minX
width = width if (width > 0) else 0
height = maxY-minY
height = height if (height > 0) else 0
v = width*height
print(v)

### FIXED CODE ###

nums = sorted(list(map(int, input().split())))
result = 'Yes' if (nums[0] + nums[1] == nums[2]) else 'No'
print(result)
N=int(input())
H=list(map(int,input().split()))
ans="Yes"
for i in range(N):
  if H[i+1]-H[i]>=0:
    continue
  elif H[i+1]-H[i]==-1:
    if H[i]-1>=H[i-1]:
      H[i]-=1
      continue
    else:
      ans="No"
      break
  else:
    ans="No"
    break
print(ans)

### FIXED CODE ###

N=int(input())
H=list(map(int,input().split()))[::-1]
ans="Yes"
for i in range(N-2):
  if H[i]-H[i+1]>=0:
    continue
  elif H[i]-H[i+1]==-1:
    H[i+1]-=1
  else:
    ans="No"
    break
print(ans)
a,b,h=map(int,input().split())
print(int((a+b)*h/2))

### FIXED CODE ###

a=int(input())
b=int(input())
h=int(input())
print(int((a+b)*h/2))
N, x = map(int, input().split())
arr = list(map(int, input().split()))

arr.sort()
cnt = 0
for ele in arr:
    if x < ele:
        break
    x -= ele
    cnt += 1

if cnt = N and x != 0:
    cnt -= 1

print(cnt)


### FIXED CODE ###

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

arr.sort()
cnt = 0
for ele in arr:
    if x < ele:
        break
    x -= ele
    cnt += 1

if cnt == N and x > 0:
    cnt -= 1

print(cnt)