A Martian boy is named s — he has got this name quite recently from his parents for his coming of age birthday. Now he enjoys looking for his name everywhere. If he sees that he can obtain his name from some string by removing zero or more letters (at that, the remaining letters remain in the same order), he gets happy. For example, if s=«aba», then strings «baobab», «aabbaa», «helloabahello» make him very happy and strings «aab», «baaa» and «helloabhello» do not.

However rather than being happy once, he loves twice as much being happy twice! So, when he got string t as a present, he wanted to cut it in two parts (the left part and the right part) so that each part made him happy.

Help s determine the number of distinct ways to cut the given string t into two parts in the required manner.


-----Input-----

The first line contains string s, consisting of lowercase English letters. The length of string s is from 1 to 1000 letters.

The second line contains string t, that also consists of lowercase English letters. The length of string t is from 1 to 10^6 letters.


-----Output-----

Print the sought number of ways to cut string t in two so that each part made s happy. 


-----Examples-----
Input
aba
baobababbah

Output
2

Input
mars
sunvenusearthmarsjupitersaturnuranusneptune

Output
0

Difficulty: interview

Starter code:

Solutions:
s = input()
pole = input()
t = 0
count = 0
for i in range(len(pole)):
    if pole[i] == s[t]:
        t += 1
    if t == len(s):
        break
    count += 1
t -= 1
for i in range(len(pole) - 1, -1, -1):
    if pole[i] == s[t]:
        t -= 1
    if t == -1:
        count1 = i
        break
if count1 - count > 0:
    print(count1 - count)
else:
    print(0)

def main():
    s = input()
    t = input()
    i, j, m, l = 0, len(t) - 1, 0, len(s) - 1
    while i < j:
        if m != len(s):
            if t[i] == s[m]:
                m += 1 
            if m != len(s):
                i += 1
        if l != -1:
            if t[j] == s[l]:
                l -= 1
            if l != -1:
                j -= 1
        if m == len(s) and l == -1:
            print(j-i)
            break
    else:
        print(0)
        
def __starting_point():
    main()

__starting_point()

__author__ = 'Руслан'
name = input()
finder = input()
left_pos = 0
right_pos = len(finder)
isfind = True
for i in name:
    left_pos = finder.find(i, left_pos)
    if left_pos == -1:
        isfind = False
        break
    else:
        left_pos += 1


if isfind:
    for i in name[::-1]:
        right_pos = finder.rfind(i, 0, right_pos)

if right_pos >= left_pos and isfind:
    print(right_pos - left_pos+1)
else:
    print(0)

p = input() #name
s = input()
answer = 0
j = 0
mini = 0
maxi = 0
lengthP = len(p)
lengthS = len(s)
for i in range(lengthS):
    if s[i] == p[j]:
        j += 1
        if j == lengthP:
            j = 0
            answer += 1
            if answer == 1:
                mini = i
if answer > 1:
    j = lengthP - 1
    for i in range(lengthS-1,-1,-1):
        if s[i] == p[j]:
            j -= 1
            if j == -1:
                maxi = i
                break
if answer == 1 or answer == 0:
    print(0)
else:
    print(maxi-mini)

s = input().rstrip()
line = input().rstrip()
i = 0
il = 0
while i != len(s) and il < len(line):
    if s[i] == line[il]:
        i += 1
    il += 1
x = il - 1
i = len(s) - 1
il = len(line) - 1
while i >= 0 and il >= 0:
    if s[i] == line[il]:
        i -= 1
    il -= 1
y = il + 1
if y - x > 0:
    print(y - x)
else:
    print(0)

class word:
    l, r = -1, -1

left_word = word()
right_word = word()

subs = input()
s = input()

pos = 0
for i in range(len(s)):
    if s[i] == subs[pos]:
        if pos == 0:
            left_word.l = i
        if pos == len(subs) - 1:
            left_word.r = i
            break
        
        pos += 1
 
pos = len(subs) - 1
for i in range(len(s) - 1, -1, -1):
    if s[i] == subs[pos]:
        if pos == len(subs) - 1:
            right_word.r = i
        if pos == 0:
            right_word.l = i
            break                        
            
        pos -= 1   
        
print(max(0, right_word.l - left_word.r))



name = input()
line = input()

i_name = 0
i_line = 0

while i_name < len(name) and i_line < len(line):
    if name[i_name] == line[i_line]:
        i_name += 1
    i_line += 1

j_name = len(name) - 1
j_line = len(line) - 1

while j_name >= 0 and j_line >= 0:
    if name[j_name] == line[j_line]:
        j_name -= 1
    j_line -= 1

if i_line <= j_line:
    print(j_line - i_line + 2)
elif i_line - 1 == j_line:
    print(1)
else:
    print(0)


import sys

t = sys.stdin.readline().strip()
s = sys.stdin.readline().strip()

t_pos = 0
first = None
for i, c in enumerate(s):
    if c == t[t_pos]:
        t_pos += 1
        if t_pos == len(t):
            first = i
            break

t_pos = len(t) - 1
last = None
for i, c in reversed(list(enumerate(s))):
    if c == t[t_pos]:
        t_pos -= 1
        if t_pos == -1:
            last = i
            break

if first == None or last == None or first > last:
    sys.stdout.write('0\n')
else:
    sys.stdout.write(str(last - first) + '\n')


name = input()
stroka = input()
lengthName = len(name)
lengthStroka = len(stroka)
indexFirst = 0
indexLast = 0
for i in range(lengthName):
    j = 0
    while((j + indexFirst) != lengthStroka):
        if stroka[j + indexFirst] == name[i]:
            indexFirst = j + indexFirst + 1
            break
        j+= 1
i = 0    
stroka = stroka[::-1]
name = name[::-1]
for i in range(lengthName):
    j = 0
    while((j + indexLast) != lengthStroka):
        if stroka[j + indexLast] == name[i]:
            indexLast = j + indexLast + 1
            break
        j+= 1
if (lengthStroka - indexLast - indexFirst + 1)<0:
    print(0)
else:
    print(lengthStroka - indexLast - indexFirst + 1)


import sys

s = input()
t = input()

has = True

index_old = -1
for i in list(s):
    index = t.find(i, index_old+1)
    has = index > index_old 
    index_old = index
    if (not has):
        print(0)
        return

left = index_old + 1
index_old = len(t)
for i in s[::-1]:
    index = t.rfind(i,left,index_old)
    has = (index != -1 and index < index_old)
    index_old = index
    if (not has):
        print(0)
        return

print(index_old-left+1)


s=input()
a=input()
j=0
v=0
c=0
flag=0
if len(s)>len(a):
    pass
else:
    for i in range(len(s)):
        k=s[i]
        while j<len(a):
            if a[j]==k:
                flag+=1
                if flag==len(s):
                    c=j
                    break
                else:
                    break
            j+=1
        j+=1
    j=len(a)-1
    flag=0
    for i in range(len(s)-1,-1,-1):
        k=s[i]
        while j>c:
            if a[j]==k:
                flag+=1
                if flag==len(s):
                    v=j-c
                    break
                else:
                    break
            j-=1
        j-=1
print(v)


name = input()
text = input()


def fun():
    first_end = len(text)
    last_start = 0
    current_index = 0
    for i in range(len(text)):
        if text[i] == name[current_index]:
            current_index += 1
            if current_index == len(name):
                first_end = i
                break
    current_index = len(name) - 1
    for i in range(len(text) - 1, first_end, -1):
        if text[i] == name[current_index]:
            current_index -= 1
            if current_index == -1:
                last_start = i
                break
    diff = last_start - first_end
    if diff < 1:
        print('0')
    else:
        print(diff)


fun()


__author__ = 'ruckus'

s = input()
t = input()
inlines = []
j = 0
for i in range(len(t)):
    if t[i] == s[j]:
        if j == 0:
            inlines.append([i])
        j += 1
        if j >= len(s):
            inlines[len(inlines)-1].append(i)
            break
j = len(s)-1
for i in range(len(t)-1, -1, -1):
    if t[i] == s[j]:
        if j == len(s)-1:
            inlines.append([i])
        j -= 1
        if j < 0:
            inlines[1].append(i)
            break
if len(inlines) < 2 or len(inlines[1]) < 2 or inlines[1][1]-inlines[0][1] < 0:
    print(0)
else:
    print(inlines[1][1]-inlines[0][1])

name = input()
phrase = input()
pos = []
j = 0
len_name = len(name)
len_phrase = len(phrase)
test = False
if len_name>=len_phrase:
    print(0)
    return
for n, i in enumerate(phrase):
    if name[j] == i:
        if not test:
            pos.append([n])
            test = True
        j += 1
        if j == len_name:
            pos[-1].append(n)
            test = False
            break

j = 0

for n, i in enumerate(phrase[::-1]):
    if name[len_name-1-j] == i:
        if not test:
            pos.append([len_phrase-n-1])
            test = True
        j += 1
        if j == len_name:
            pos[-1].append(len_phrase-n-1)
            test = False
            break

if pos[0][1] < pos[1][1]:
    print(pos[1][1] - pos[0][1])
else:
    print(0)

s=input()
t=input()
if len(t)<=len(s):
    print(0)
elif len(s)==1:
    p1=t.find(s)
    p2=t.rfind(s)
    if p2-p1==0:
        print(0)
    else:
        print(p2-p1)
else:
    p1=0    
    for i in range(len(s)):
        while s[i]!=t[p1]:
            p1+=1
        else:
            p1+=1
    p1-=1
    p2=len(t)-1
    for i in range(len(s)-1,-1,-1):
        while s[i]!=t[p2]:
            p2-=1
        else:
            p2-=1
    p2+=1
    if p2-p1<=0:
        print(0)
    else:
        print(p2-p1)

def go(s, t):
    sb = None
    si = 0
    for i in range(len(t)):
        if t[i] == s[si]:
            si += 1
            if si == 1:
                sb = (i,)
            if si == len(s):
                sb += (i,)
                return sb
    return None

s = input()
t = input()

si = 0
f = go(s, t)
s = [x for x in reversed(s)]
t = [x for x in reversed(t)]
l = go(s, t)

print((len(t) - l[1] - 1) - f[1] if f and l and (len(t) - l[1] - 1) - f[1] > 0 else 0)

s1 = input().rstrip()
s2 = input().rstrip()
len1 = len(s1)
len2 = len(s2)
l = 1
r = 0
got = 0
for i in range(0,len2):
    if s2[ i ] == s1[ got ] :
        got = got + 1
        if got == len1 :
            l = i
            break
got = len1 - 1
for j in range(0,len2):
    i = len2 - j - 1
    if s2[ i ] == s1[ got ] :
        got = got - 1
        if got < 0 :
            r = i - 1
            break
if l <= r :
    print( r - l + 1 )
else :
    print( "0" )


s1 = input()
s2 = input()
len1 = len(s1)
len2 = len(s2)
l = 1
r = 0
got = 0
for i in range(0,len2):
    if s2[ i ] == s1[ got ] :
        got = got + 1
        if got == len1 :
            l = i
            break
got = len1 - 1
for j in range(0,len2):
    i = len2 - j - 1
    if s2[ i ] == s1[ got ] :
        got = got - 1
        if got < 0 :
            r = i - 1
            break
if l <= r :
    print( r - l + 1 )
else :
    print( "0" )


def search_podstroki(t,s):
    c1 = 0
    for i in range(len(t)):
        if (t[i] == s[0]):
            s = s[1::]
            if (len(s) == 0):
                c1 = -1
                return i+1
    if (c1 == 0):
        return -1
            







s = input()
t = input()
e = 0
if (len(t) <= len(s)):
    print('0')
else:
    s1 = s
    h = search_podstroki(t,s1)
    s1 = s1[::-1]
    t = t[::-1]
    g = search_podstroki(t,s1)
    if ((g == -1) or (h == -1)):
        print('0')
    else:
        g = (len(t) - g) + 1
        if (g < h):
            print('0')
        else:
            print(g-h)

#! /usr/bin/python3


    
def solve():
    s = input()
    t = input()
    
    ls = len(s)
    if s[ls - 1] == '\n':
        ls = ls - 1
    lt = len(t)
    if t[lt - 1] == '\n':
        lt = lt - 1
    
    #print("ls = ",ls," lt = ", lt)
    i = 0
    j = 0
    pos = -1
    while 1:
        if s[i] == t[j]:
            i = i + 1
            j = j + 1
        else:
            j = j + 1
        
        if i == ls:
            pos = j
        
        if i == ls or j == lt:
            break
    
    if pos == -1:
        print(0)
        return
    i = ls - 1
    j = lt - 1
    reverse = -1
    
    while 1:
        if s[i] == t[j]:
            i = i - 1
            j = j - 1
        else:
            j = j - 1
        
        if i == -1:
            reverse = j
        
        if i == -1 or j == -1:
            break
    # print("pos = ",pos,"  reverse = ", reverse)
    reverse = reverse + 1
    pos = pos - 1
    if reverse == -1 or reverse < pos:
        print(0)
    else:
        print(reverse - pos)
        
solve()

from functools import reduce
from operator import *
from math import *
from sys import *
from string import *
from collections import *
setrecursionlimit(10**7)
dX= [-1, 1, 0, 0,-1, 1,-1, 1]
dY= [ 0, 0,-1, 1, 1,-1,-1, 1]
RI=lambda: list(map(int,input().split()))
RS=lambda: input().rstrip().split()
#################################################
def findMatch(a,b):
    i,j=0,0
    while i<len(a) and j<len(b):
        if a[i]==b[j]:
            j+=1
        i+=1
    return i
s=RS()[0]
t=RS()[0]
x=findMatch(t,s)
y=len(t)-findMatch(t[::-1],s[::-1])
print( max(y-x+1, 0))






t = input()
s = input()
l_t = len(t)
l_s = len(s)
x = 0
f = l_s+1
for i in range(l_s):
    if t[x] == s[i]: x += 1
    if x == l_t:
        f = i
        break
c = -1
y = l_t-1
for i in range(l_s-1,-1,-1):
    if t[y] == s[i]: y -= 1
    if y == -1:
        c = i
        break
if c - f <= 0: print(0)
else: print(c - f)



name = input()
s = input()

name_len = len(name)
l = -1
r = len(s)

index = 0
for ch in s:
    l += 1
    if ch == name[index]:
        index += 1
    if index == name_len:
        break

index = name_len - 1
for ch in s[::-1]:
    r -= 1
    if ch == name[index]:
        index -= 1
    if index == -1:
        break

if l < r:
    print(r - l)
else:
    print(0)

t = input()
s = input()
l_t = len(t)
l_s = len(s)
x = 0
f = l_s+1
for i in range(l_s):
    if t[x] == s[i]: x += 1
    if x == l_t:
        f = i
        break
c = -1
y = l_t-1
for i in range(l_s-1,-1,-1):
    if t[y] == s[i]: y -= 1
    if y == -1:
        c = i
        break
if c - f <= 0: print(0)
else: print(c - f)


s = input()
t = input()

position_left = 0
seen_left = 0

while seen_left < len(s) and position_left < len(t):
    if t[position_left] == s[seen_left]:
        seen_left += 1
    position_left += 1

if seen_left < len(s):
    print(0)
    return

position_right = len(t) - 1
seen_right = 0

while seen_right < len(s) and position_right >= 0:
    if t[position_right] == s[len(s) - seen_right - 1]:
        seen_right += 1
    position_right -= 1

if position_left <= position_right:
    print(position_right - position_left + 2)
else:
    print(0)