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.util.*;
import java.io.*;
public class codeforces{
    // Input
    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;
        public InputReader() {
            reader = new BufferedReader(new InputStreamReader(System.in));
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public String nextLine() {
            String s = null;
            try {
                s = reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
            return s;
        }

        public String nextParagraph() {
            String line = null;
            String ans = "";
            try {
                while ((line = reader.readLine()) != null) {
                    ans += line;
                }
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
            return ans;
        }
    }
    //Template
    static int mod = 998244353;
    static void printArray(int ar[]){ for(int x:ar) System.out.print(x+" ");}
    static void printArray(ArrayList<Integer> ar){ for(int x:ar) System.out.print(x+" ");}
    static long gcd(long a, long b){ if (a == 0) return b; return gcd(b%a, a);}
    static long power(long x, long y, int p) { long res = 1; x = x % p;  while (y > 0) { if((y & 1)==1) res = (res * x) % p; y = y >> 1;x = (x * x) % p;  } return res;}
    static void takeArrayInput(InputReader sc, int ar[]){ for(int i=0;i<ar.length;i++) ar[i]=sc.nextInt(); }
    static void takeArrayInput(InputReader sc, long ar[]){ for(int i=0;i<ar.length;i++) ar[i]=sc.nextLong(); }
    static void take2dArrayInput(InputReader sc, int ar[][]){ for(int i=0;i<ar.length;i++) for(int j=0;j<ar[i].length;j++) ar[i][j]=sc.nextInt(); }
    static void take2dArrayInput(InputReader sc, long ar[][]){ for(int i=0;i<ar.length;i++) for(int j=0;j<ar[i].length;j++) ar[i][j]=sc.nextLong(); }
    static ArrayList<ArrayList<Integer>> graph(InputReader sc, int n, int m){
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        for(int i=0;i<n;i++) list.add(new ArrayList<Integer>());
        for(int i=0;i<m;i++){ int u = sc.nextInt(); int v = sc.nextInt(); list.get(u).add(v); list.get(v).add(u); }
        return list;
    }
    // Write Code Here
    static class Data {
        int u;
        int v;
        public Data(int e, int val) {
            this.u = e;
            this.v = val;
        }
    }
    static void sieveOfEratosthenes(int n, ArrayList<Integer> pr) {
        // Create a boolean array "prime[0..n]" and initialize
        // all entries it as true. A value in prime[i] will
        // finally be false if i is Not a prime, else true.
        boolean prime[] = new boolean[n + 1];
        for (int i = 0; i < n; i++)
            prime[i] = true;
        for (int p = 2; p * p <= n; p++) {
            // If prime[p] is not changed, then it is a prime
            if (prime[p] == true) {
                // Update all multiples of p
                pr.add(p);
                for (int i = p * p; i <= n; i += p)
                    prime[i] = false;
            }
        }
    }
    static int longest(String s, String t){
        int p[] = new int[t.length()];
        int i=0, j=0;
        for(i=0;i<s.length() && j<t.length();i++){
            if(s.charAt(i) == t.charAt(j)){
                p[j++]=i;
            }
        }
        j = t.length()-1;
        int max = s.length() - p[j] -1;
        char c = t.charAt(j);
        for(i=s.length()-1;i>=0 && j>0;i--){
            if(s.charAt(i) == c){
                int k = p[j-1];
                max = Math.max(max, (i-k-1));
                j--;
                c = t.charAt(j);
            }
        }
        return max;
    }
    public static void main(String args[]) {
        InputReader sc = new InputReader();
        PrintWriter pw = new PrintWriter(System.out);
        int i=0, j=0;
        String s = sc.nextLine();
        String t = sc.nextLine();
        int m = longest(s, t);
        StringBuilder sb = new StringBuilder(s);
        s = sb.reverse().toString();
        sb = new StringBuilder(t);
        t = sb.reverse().toString();
        int p = longest(s, t);
        pw.println(Math.max(p, m));
        pw.close();
    }
}