Problem

Given the strings $ s $, $ t $.
First, let the string set $ A = $ {$ s $}, $ B = \ phi $.
At this time, I want to perform the following operations as much as possible.

operation

step1

Perform the following processing for all $ u ∊ A $.

1. From all subsequences of $ u $ (not necessarily contiguous), choose any one that is equal to $ t $. Let the indexes corresponding to $ u $ of the selected subsequence be $ z_1 $, $ z_2 $,…, $ z_ {| t |} $ (however, 1 $ \ le $ $ z_1 $ $ \ lt $ $ z_2). $$ \ lt $… $ \ lt $ $ z_ {| t |} $ $ \ le $ $ | u | $). If there is no such subsequence, the operation ends.


2. Divide the original string with the selected substring characters $ u_ {z_1} $, $ u_ {z_2} $,…, $ u_ {z_ {| t |}} $ and convert them to $ B $ to add.

For example, in the case of $ u = $ "abcdcd" and $ t = $ "ac", the following two division methods can be considered.
If you choose the first and third characters of $ u $, it will be split into "", "b" and "dcd".
If you choose the first and fifth characters of $ u $, it will be split into "", "bcd" and "d".


step2

Replace $ A $ with $ B $ and empty $ B $.
Increase the number of operations by 1.

Subsequence example

The subsequences of "abac" are {"", "a", "b", "c", "aa", "ab", "ac", "ba", "bc", "aac", "aba" "," abc "," bac "," abac "}.
"a" is a subsequence created by extracting the first or third character of "abac".
"ac" is a subsequence created by extracting the 1st and 4th characters of "abac" or the 3rd and 4th characters.

Constraints

The input satisfies the following conditions.

* 1 $ \ le $ $ | t | $ $ \ le $ $ | s | $ $ \ le $ $ 10 ^ 5 $
* Characters contained in the strings $ s $ and $ t $ are uppercase or lowercase letters of the alphabet

Input

The input is given in the following format.


$ s $
$ t $


The string $ s $ is given on the first line, and the string $ t $ is given on the second line.

Output

Output the maximum number of operations.

Examples

Input

AABABCAC
A


Output

2


Input

abaabbabaabaabbabbabaabbab
ab


Output

3


Input

AbCdEfG
aBcDeFg


Output

0
#include <bits/stdc++.h>
using namespace std;
#define _MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) _MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define mp make_pair
#define pb push_back
#define all(x) begin(x),end(x)
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cerr<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cerr<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

char tmp_str[2][100005];

int solve(){
  string s,t;
  cin>>s>>t;

  if(s.size() == t.size()){
    if(s==t) return 1;
    else return 0;
  }

  int r = 1;
  int cur = t.size();
  while(s.size() >= cur){
    cur += (cur+1)*t.size();
    r++;
  }

  auto f = [&](int x){
    if(x==0) return true;
    auto s1 = tmp_str[0];
    auto s2 = tmp_str[1];
    int p_size = 0;
    int q_size = 0;
    rep(i,x){
      q_size = 0;
      rep(j,p_size) s2[q_size++] = s1[j];
      rep(j,t.size()){
        s2[q_size++] = t[j];
        rep(k,p_size) s2[q_size++] = s1[k];
      }
      swap(s1, s2);
      swap(p_size, q_size);
    }
    // dbg(x,string(s1, s1+p_size));
    int is=0,it=0;
    while(is<s.size() && it<p_size){
      if(s[is] == s1[it]){
        is++; it++;
      } else {
        is++;
      }
    }
    return it == p_size;
  };

  int l=0;
  while(r-l>1){
    int mid = (l+r)/2;
    if(f(mid)) l = mid;
    else r = mid;
  }
  return l;
}


int main(){
  cout << solve() << endl;

  return 0;
}

