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
#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  string s, t;
  cin >> s >> t;

  string now = t;
  REP(i, 30) {
    // sの中にnowが含まれるか判定
    int cnt = 0;
    REP(j, s.size()) if(cnt < now.size() && s[j] == now[cnt]) cnt++;
    if(cnt < now.size()) {
      cout << i << endl;
      return 0;
    }
    int n_sz = now.size() * t.size() + now.size() + t.size();
    if(n_sz > s.size()) {
      cout << i+1 << endl;
      return 0;
    }
    string n = now;
    REP(j, t.size()) n += t[j] + now;
    now = n;
  }

  return 0;
}

