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.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main { // See rules of OJ at the bottom

  private static final PrintStream OUT = System.out;

  public static void main(String[] args) throws IOException {

    // io.getInt(), io.getLine(), io.getWord()
    Main main = new Main();
    try (IO io = new IO(System.in, System.out)) {
      String A = io.getLine(), B = io.getLine();
      io.println(main.solve(A, B));
    }
  }

  private int solve(final String A, final String B) {
    int[] dp1 = new int[B.length()];
    for (int i = 0, j = 0; i != A.length(); i++)
      if (A.charAt(i) == B.charAt(j)) {
        dp1[j++] = i;
        if (j == B.length())
          break;
      }
    int[] dp2 = new int[B.length()];
    for (int i = A.length() - 1, j = B.length() - 1; i != -1; i--) {
      if (A.charAt(i) == B.charAt(j)) {
        dp2[j--] = i;
        if (j == -1)
          break;
      }
    }
    int res = A.length() - 1 - dp1[dp1.length - 1];
    res = Math.max(res, dp2[0]);
    for (int i = 0, j = 1; j != B.length(); i++, j++) 
      res = Math.max(res, dp2[j] - dp1[i] - 1);
    return res;
  }


  ////////////////

  // @formatter:off
  private void debug(Object... o) { OUT.println(Arrays.deepToString(o)); }
  private static class Unused { // purpose is for the import to stay
    private Set<Integer> set = new HashSet<>();
    private Map<Integer, Integer> map = new HashMap<>();
    private List<Integer> list = Arrays.asList();
    private Queue<Integer> q = new ArrayDeque<>();
    private PriorityQueue<Integer> pq;
    private Stack<Integer> stack;
    private TreeMap<Integer, Integer> tmap;
    private TreeSet<Integer> tset;
    private Matcher m;
    private Pattern P;
    private void _unused() {
      // Math.ceil(3d);
      // Math.floor(3d);
      // Math.log(10d);
      // Arrays.binarySearch(arr, fromIndex, toIndex_exclusive, key);
    }
    private long inv1(long base, final long MOD) {
      long res = 1L; base = base % MOD;
      for (long exponent = MOD - 2L; exponent != 0; exponent >>>=1) {
        if ((exponent & 1) == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
      }
      return res;
    }
    private long[] invN(final int N, final long MOD) {
      long[] res = new long[N + 1]; if (N >= 1) res[1] = 1;
      for (int i = 2; i <= N; i++) res[i] = ((MOD - MOD / i) * res[(int) (MOD % i)]) % MOD;
      return res;
    }
  }

  // to detect input EOF example
  // String line = null;  while ((line = io.getLine()) != null) { /* parse line and do your computation */ }

  private static class IO extends PrintWriter {
    public IO(InputStream i) {
      super(new BufferedOutputStream(System.out)); r = new BufferedReader(new InputStreamReader(i));
    }
    public IO(InputStream i, OutputStream o) {
      super(new BufferedOutputStream(o)); r = new BufferedReader(new InputStreamReader(i));
    }
    public boolean hasMoreTokens() { return peekToken() != null; }
    public int getInt() { return Integer.parseInt(nextToken()); }
    public int[] getArray(final int N) {
      int[] nums = new int[N];
      for (int i = 0; i != N; i++)
        nums[i] = getInt();
      return nums;
    }
    public int[][] getMatrix(final int R, final int C) {
      int[][] mat = new int[R][C];
      for (int r = 0; r != R; r++)
        for (int c = 0; c != C; c++)
          mat[r][c] = getInt();
      return mat;
    }    
    public double getDouble() { return Double.parseDouble(nextToken()); }
    public float getFloat() { return Float.parseFloat(nextToken()); }
    public long getLong() { return Long.parseLong(nextToken()); }
    public String getWord() { return nextToken(); }
    public String getLine() { try { return r.readLine(); } catch (IOException e) { return null; } }
    private BufferedReader r; private StringTokenizer st; private String token;
    private String peekToken() {
      if (token == null)
        try {
          while (st == null || !st.hasMoreTokens()) {
            String line = r.readLine(); if (line == null) return null; st = new StringTokenizer(line);
          }
          token = st.nextToken();
        } catch (IOException e) {}
      return token;
    }
    private String nextToken() {
      String ans = peekToken(); token = null; return ans;
    }
  }
  // @formatter:on

  // atcoder USACO require no package of a class named: Main
  // Google code jam requires no package of a class named: Solution
  // Kattis click submit from the problem, paste code in, and specify Main class as Main
  // CodeForce LightOJ click submit from the problem, paste code in.
}
