The only difference between easy and hard versions is the length of the string.

You are given a string s and a string t, both consisting only of lowercase Latin letters. It is guaranteed that t can be obtained from s by removing some (possibly, zero) number of characters (not necessary contiguous) from s without changing order of remaining characters (in other words, it is guaranteed that t is a subsequence of s).

For example, the strings "test", "tst", "tt", "et" and "" are subsequences of the string "test". But the strings "tset", "se", "contest" are not subsequences of the string "test".

You want to remove some substring (contiguous subsequence) from s of maximum possible length such that after removing this substring t will remain a subsequence of s.

If you want to remove the substring s[l;r] then the string s will be transformed to s_1 s_2 ... s_{l-1} s_{r+1} s_{r+2} ... s_{|s|-1} s_{|s|} (where |s| is the length of s).

Your task is to find the maximum possible length of the substring you can remove so that t is still a subsequence of s.

Input

The first line of the input contains one string s consisting of at least 1 and at most 2 ⋅ 10^5 lowercase Latin letters.

The second line of the input contains one string t consisting of at least 1 and at most 2 ⋅ 10^5 lowercase Latin letters.

It is guaranteed that t is a subsequence of s.

Output

Print one integer — the maximum possible length of the substring you can remove so that t is still a subsequence of s.

Examples

Input


bbaba
bb


Output


3


Input


baaba
ab


Output


2


Input


abcde
abcde


Output


0


Input


asdfasdf
fasd


Output


3
import java.io.*;
import java.lang.reflect.Array;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.text.DecimalFormat;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;


public class Main
{	
   static long mod=(long)(1e+9 + 7);
	
   //static long mod=(long)998244353;
   static int[] sieve;
   static ArrayList<Integer> primes;
   static PrintWriter out;
   static fast s;
   static StringBuilder fans;
   
   static int x_dir[];
   static int y_dir[];

   
   public static void solve()
   {
   	char ch1[]=s.nextLine().toCharArray();
   	char ch2[]=s.nextLine().toCharArray();
   	
   	int n=ch1.length; int m=ch2.length;
   	
   	ArrayList<Integer> start=new ArrayList<Integer>();
   	ArrayList<Integer> end=new ArrayList<Integer>();
   	
   	int j=0; 
   	for(int i=0;i<n;i++)
   		if(j<m && ch1[i]==ch2[j]) {start.add(i);j++;}
   	
   	j=m-1;
   	for(int i=n-1;i>=0;i--)
   		if(j>=0 && ch1[i]==ch2[j]) {end.add(i);j--;}
   	
   	int max=Math.max(n-1-start.get(m-1), end.get(m-1));
   	for(int i=0;i<start.size()-1;i++) max=Math.max(max, end.get(end.size()-1-i-1)-start.get(i)-1);
   	fans.append(max);
   }
   
   public static void main(String[] args) throws java.lang.Exception
   {	  	
	     s = new fast();
	     
	     out=new PrintWriter(System.out);
	     fans=new StringBuilder("");
		  
	     int t=1;
	     
	     while(t>0)
	    	 {
	    		 solve();
	    		 t--;
	    	 }
	    
	    out.println(fans);
	    out.close();
   }
  
 
 
static class fast {   
	
	   private InputStream i;
		private byte[]  buf = new byte[1024];
		private int curChar;
		
		private int numChars;
		
		//Return floor log2n
		public static long log2(long bits) // returns 0 for bits=0
			{
			    int log = 0;
			    if( ( bits & 0xffff0000 ) != 0 ) { bits >>>= 16; log = 16; }
			    if( bits >= 256 ) { bits >>>= 8; log += 8; }
			    if( bits >= 16  ) { bits >>>= 4; log += 4; }
			    if( bits >= 4   ) { bits >>>= 2; log += 2; }
			    return log + ( bits >>> 1 );
			}
		
		public static boolean next_permutation(int a[])
		   {
			   int i=0,j=0;int index=-1;	   
			   int n=a.length;
			   
			   for(i=0;i<n-1;i++)
				   if(a[i]<a[i+1]) index=i;
			   
			   if(index==-1) return false;
			   i=index;
 
			  
			   for(j=i+1;j<n && a[i]<a[j];j++);
 
			   int temp=a[i];
			   a[i]=a[j-1];
			   a[j-1]=temp;
			   	   
			   for(int p=i+1,q=n-1;p<q;p++,q--)
			   {
				   temp=a[p];
				   a[p]=a[q];
				   a[q]=temp;
			   }
			   
			   return true;
		   }
		   
		public static void sieve(int size)
		{
			sieve=new int[size+1];
			
			primes=new ArrayList<Integer>();
			
			sieve[1]=1;
			
			for(int i=2;i*i<=size;i++)
			{
				if(sieve[i]==0)
				 {
					for(int j=i*i;j<size;j+=i) {sieve[j]=1;}
				 }
			}
			
			for(int i=2;i<=size;i++)
			{
				if(sieve[i]==0) primes.add(i);
			}
		}
		
		public static long pow(long a, long p){
		    long o = 1;
		    for(; p>0; p>>=1){
		        if((p&1)==1)o = mul(o, a);
		        a = mul(a, a);
		    }
		    return o;
		}
		
		public static long add(long... a){
		    long o = 0;
		    for(long x:a)o = (o+mod+x)%mod;
		    return o;
		}
		
		public static long mul(long... a){
		    long p = 1;
		    for(long x:a)p = (mod+(p*x)%mod)%mod;
		    return p;
		}
		
		public static long mod_inv(long n)
		{
			return pow(n,mod-2);
		}
		   
		public long gcd(long r,long ans)
		{
			if(r==0) return ans;
			return gcd(ans%r,r);
		}
		
		public fast() {
			this(System.in);
		}
		public fast(InputStream is) {
			i = is;
		}
		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = i.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}
		public String nextLine() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndOfLine(c));
			return res.toString();
		}
		public String nextString() {
     		int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}
		public long nextLong() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
		public int nextInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
		public boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
		public boolean isEndOfLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}
 
	}	
}