The unlucky Ikta-kun has rewritten the important character string T that he had to a different character string T'by the virus. It is known that the virus has rewritten one letter of T to a different letter. That is, T and T'are different by exactly one character. In order to restore T, Ikta prepared a document S in which T appears. As a preparation for restoring T, I would like to find out the number of substrings of S that may match T.

Given the string T'and the document S. S = a1 a2 a3 .. .a | S | length | T'| substring ak ak + 1 ... ak + | T'| −1 (1 ≤ k ≤ | S | − | T'| Find the number of things that differ by one character from T'in +1).



Input

The input is given in the following format.


S
T'


* S is given in the first line.
* T'is given in the second line.
* S and T'consist only of uppercase and lowercase alphabets, respectively.



Constraints

Each variable being input satisfies the following constraints.

* 1 ≤ | S | ≤ 300,000
* 1 ≤ | T'| ≤ | S |

Output

Output the number of substrings that satisfy the conditions on one line.

Examples

Input

abcbcdbc
abc


Output

2


Input

aaaaaa
aaaaaa


Output

0


Input

baaaaaaaa
b


Output

8
#include <bits/stdc++.h>

using namespace std;

struct SuffixArray
{
  vector< int > SA;
  string s;

  void Build_SA(const string &str)
  {
    s = str;
    SA.resize(s.size());
    iota(begin(SA), end(SA), 0);
    sort(begin(SA), end(SA), [&](const int &a, const int &b)
    {
      if(s[a] == s[b]) return (a > b);
      return (s[a] < s[b]);
    });
    vector< int > classes(s.size()), c(s.size()), cnt(s.size());
    for(int i = 0; i < s.size(); i++) {
      c[i] = s[i];
    }
    for(int len = 1; len < s.size(); len <<= 1) {
      classes[SA[0]] = 0;
      for(int i = 1; i < s.size(); i++) {
        if(c[SA[i - 1]] == c[SA[i]] && SA[i - 1] + len < s.size() && c[SA[i - 1] + (len >> 1)] == c[SA[i] + (len >> 1)]) {
          classes[SA[i]] = classes[SA[i - 1]];
        } else {
          classes[SA[i]] = i;
        }
      }
      iota(begin(cnt), end(cnt), 0);
      copy(begin(SA), end(SA), begin(c));
      for(int i = 0; i < s.size(); i++) {
        int s1 = c[i] - len;
        if(s1 >= 0) SA[cnt[classes[s1]]++] = s1;
      }
      classes.swap(c);
    }
  }

  int operator[](int k) const
  {
    return (SA[k]);
  }

  int size() const
  {
    return (s.size());
  }

  bool lt_substr(string &t, int si = 0, int ti = 0)
  {
    int sn = s.size(), tn = t.size();
    while(si < sn && ti < tn) {
      if(s[si] < t[ti]) return (true);
      if(s[si] > t[ti]) return (false);
      ++si, ++ti;
    }
    return (si >= sn && ti < tn);
  }

  int lower_bound(string &t)
  {
    int low = -1, high = SA.size();
    while(high - low > 1) {
      int mid = (low + high) >> 1;
      if(lt_substr(t, SA[mid])) low = mid;
      else high = mid;
    }
    return (high);
  }

  pair< int, int > lower_upper_bound(string &t)
  {
    int idx = lower_bound(t);
    int low = idx - 1, high = SA.size();
    t.back()++;
    while(high - low > 1) {
      int mid = (low + high) >> 1;
      if(lt_substr(t, SA[mid])) low = mid;
      else high = mid;
    }
    t.back()--;
    return (make_pair(idx, high));
  }
};

struct LongestCommonPrefixArray
{
  vector< int > LCP, rank;

  LongestCommonPrefixArray(SuffixArray &SA)
  {
    Build_LCP(SA);
  }

  void Build_LCP(SuffixArray &SA)
  {
    string &s = SA.s;
    rank.resize(s.size());
    for(int i = 0; i < s.size(); i++) {
      rank[SA[i]] = i;
    }
    LCP.resize(s.size() - 1);
    for(int i = 0, h = 0; i < s.size(); i++) {
      if(rank[i] + 1 < s.size()) {
        for(int j = SA[rank[i] + 1]; max(i, j) + h < s.length() && s[i + h] == s[j + h]; ++h);
        LCP[rank[i]] = h;
        if(h > 0) --h;
      }
    }
  }

  int operator[](int k) const
  {
    if(k < 0) return (0);
    return (LCP[k]);
  }

  int size() const
  {
    return (LCP.size() + 1);
  }
};

struct SegmentTreeLCP : LongestCommonPrefixArray
{
  const int INF = 1 << 30;
  vector< int > data;
  int sz;

  SegmentTreeLCP(SuffixArray &sa) : LongestCommonPrefixArray(sa)
  {
    sz = 1;
    while(sz < LCP.size()) sz <<= 1;
    data.assign(2 * sz - 1, INF);
    for(int i = 0; i < LCP.size(); i++) {
      data[i + sz - 1] = (*this)[i];
    }
    for(int i = sz - 2; i >= 0; i--) {
      data[i] = min(data[2 * i + 1], data[2 * i + 2]);
    }
  }

  int rmq(int a, int b, int k, int l, int r)
  {
    if(a >= r || b <= l) return (INF);
    if(a <= l && r <= b) return (data[k]);
    return (min(rmq(a, b, 2 * k + 1, l, (l + r) >> 1), rmq(a, b, 2 * k + 2, (l + r) >> 1, r)));
  }

  int rmq(int a, int b)
  {
    if(rank[a] > rank[b]) swap(a, b);
    return (rmq(rank[a], rank[b], 0, 0, sz));
  }
};


int main()
{
  string S, T;
  cin >> S >> T;

  string s = S, t = T;
  reverse(begin(s), end(s));
  reverse(begin(t), end(t));

  SuffixArray SA, RSA;
  SA.Build_SA(S + "*" + T);
  RSA.Build_SA(s + "*" + t);
  SegmentTreeLCP LCP(SA), RLCP(RSA);

  int ret = 0;
  for(int i = 0; i <= S.size() - T.size(); i++) {
    int x = LCP.rmq(i, S.size() + 1);
    int y = RLCP.rmq(S.size() - T.size() - i, S.size() + 1);
    ret += x + y == T.size() - 1;
  }
  cout << ret << endl;
}