Given are two strings s and t consisting of lowercase English letters. Determine if the number of non-negative integers i satisfying the following condition is finite, and find the maximum value of such i if the number is finite.

* There exists a non-negative integer j such that the concatenation of i copies of t is a substring of the concatenation of j copies of s.

Constraints

* 1 \leq |s| \leq 5 \times 10^5
* 1 \leq |t| \leq 5 \times 10^5
* s and t consist of lowercase English letters.

Input

Input is given from Standard Input in the following format:


s
t


Output

If the number of non-negative integers i satisfying the following condition is finite, print the maximum value of such i; if the number is infinite, print `-1`.

Examples

Input

abcabab
ab


Output

3


Input

aa
aaaaaaa


Output

-1


Input

aba
baaab


Output

0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, N) for (int i = 0; i < (int)N; i++)
#define all(a) (a).begin(), (a).end()

string s, t;
int n, m;
const int R = 256;
vector<vector<int>> dfa;
vector<int> match;
vector<int> L;

void kmp() {
  dfa.resize(R, vector<int>(m+1));
  dfa[t[0]][0] = 1;
  for(int x = 0, j = 1; j <= m; j++) {
    for(int c = 0; c < R; c++) {
      dfa[c][j] = dfa[c][x];
    }
    dfa[t[j]][j] = (j+1)%(m+1);
    x = dfa[t[j]][x];
  }
}

int pathLength(int i) {
  if(!match[i]) return 0;
  if(L[i] != -1) return L[i];

  return L[i] = pathLength((i+m)%n) + 1;
}

bool hasLoop() {
  rep(i,m) {
    bool loop = true;
    for(int j = 0; j < n + m; j += m) {
      if(!match[(i+j)%n]) loop = false;
    }
    if(loop) return true;
  }
  return false;
}

int main () {
  cin >> s >> t;
  n = s.size(), m = t.size();
  match.resize(n);
  L.resize(n, -1);

  kmp();
  for(int i = 0, j = 0; i < n + m - 1; i++) {
    j = dfa[s[i%n]][j];
    if(j == m) match[i-m+1] = 1;
  }

  if(hasLoop()) {
    cout << - 1 << endl;
    return 0;
  }

  int ans = 0;
  rep(i,n) {
    if(match[i]) ans = max(ans, pathLength(i));
  }
  cout << ans << endl;

  return 0;
}
