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;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF 1e16
#define mod 1000000007

string s,t;
int sa[100010],ta[100010];
int n,m;
int nxt[100010][52];
string b[20];
vector<int> ba[20];

int main(){
  cin>>s>>t;
  n=s.size();
  m=t.size();
  rep(i,n){
    if(s[i]>='A'&&s[i]<='Z')sa[i]=s[i]-'A';
    else sa[i]=s[i]-'a'+26;
  }
  rep(i,n){
    if(t[i]>='A'&&t[i]<='Z')ta[i]=t[i]-'A';
    else ta[i]=t[i]-'a'+26;
  }
  b[0]=t;
  rep(i,b[0].size()){
    if(b[0][i]>='A'&&b[0][i]<='Z')ba[0].push_back(b[0][i]-'A');
    else ba[0].push_back(b[0][i]-'a'+26);
  }
  repl(i,1,20){
    if(m*b[i-1].size()>n)break;
    rep(j,m){
      b[i]+=b[i-1];
      b[i]+=t[j];
    }
    b[i]+=b[i-1];
    rep(j,b[i].size()){
      if(b[i][j]>='A'&&b[i][j]<='Z')ba[i].push_back(b[i][j]-'A');
      else ba[i].push_back(b[i][j]-'a'+26);
    }
  }
  memset(nxt,-1,sizeof(nxt));
  for(int i=n-1;i>=0;i--){
    for(int j=0;j<52;j++){
      if(sa[i]==j)nxt[i][j]=i+1;
      else nxt[i][j]=nxt[i+1][j];
    }
  }
  rep(i,20){
    int crt=0;
    if(ba[i].size()==0){
      cout<<i<<endl;
      return 0;
    }
    rep(j,ba[i].size()){
      int nxti=nxt[crt][ba[i][j]];
      if(nxti<0){
        cout<<i<<endl;
        return 0;
      }
      crt=nxti;
    }
  }
  return 0;
}

