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 pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a) (a).begin(),(a).end()
#define pb emplace_back
#define INF (1e9+1)

bool isSubstr(string &s, string &t){
    int p = 0;
    rep(i,s.size()){
        if(s[i]==t[p]){
            p++;
        }
        if(p==t.size())break;
    }
    
    if(p==t.size())return true;
    else return false;
}

int main(){
    string s,t;
    
    cin>>s>>t;
    
//    vector<string> vs(18,"");
//    vs[1] = t;
//    int l = t.size();
//    for(int i=2;i<18;i++){
//        l = (l+1)*t.size() + l;
//        if(l>s.size())break;
//        vs[i] = t;
//        rep(j,vs[i-1].size()){
//            vs[i]+=string(1,vs[i-1][j]);
//            vs[i]+=t;
//        }
//        assert(l==vs[i].size());
//    }
//
//    for(int i=1;i<18;i++)if(vs[i]=="")vs[i] = "*";
    
    vector<string> vs(2);
    vs[1] = t;
    int ok = 0;
    for(int i=1;i<18;i++){
        
        if(isSubstr(s,vs[i%2]))ok = i;
        else break;
        int l = (vs[i%2].size()+1)*t.size() + vs[i%2].size();
        
        if(l>s.size())break;
        vs[(i+1)%2] = t;
        rep(j,vs[i%2].size()){
            vs[(i+1)%2] += string(1,vs[i%2][j]);
            vs[(i+1)%2] += t;
        }
    }
    cout<<ok<<endl;
}


