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 DBG cerr << '!' << endl;
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(10)
#define INF 1000000000
#define MOD 1000000007

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

string S;
string T;
int place;

bool dfs(int depth){
	if(depth <= 0)return true;
	if(!dfs(depth-1))return false;
	REP(i,T.size()){
		while(S[place] != T[i])
		{
			//cout << S[place];
			place++;
			if(place >= S.size())return false;
		}
		//cout << depth;
		place++;
		if(depth>1 && place >= S.size())return false;
		if(!dfs(depth-1))return false;
	}	
	
	return true;
}

int main()
{
	cin >> S >> T;
	//cout << S.size() << endl;
	//cout << T.size() << endl;
	int ans = 0;
	while(1){
		//cout << endl;
		place = 0;
		if(dfs(ans))ans++;
		else break;
	}
	//cout << endl;
	cout << ans-1 << endl;
	
	return 0;
}
