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;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

struct RollingHash{
    static const int MD = 3;
    static const vector<ll> hash_base, hash_mod;

    int n;
    vector<ll> hs[MD], pw[MD];

    RollingHash(){}
    RollingHash(const string &s){
        n = s.size();
        rep(i,MD){
            hs[i].assign(n+1,0);
            pw[i].assign(n+1,0);
            hs[i][0] = 0;
            pw[i][0] = 1;
            rep(j,n){
                pw[i][j+1] = pw[i][j]*hash_base[i] % hash_mod[i];
                hs[i][j+1] = (hs[i][j]*hash_base[i]+s[j]) % hash_mod[i];
            }
        }
    }

    // 1-index
    ll hash_value(int l, int r, int i){
        return ((hs[i][r] - hs[i][l]*pw[i][r-l])%hash_mod[i]+hash_mod[i])%hash_mod[i];
    }

    bool match(int l1, int r1, int l2, int r2){
        bool ret = true;
        rep(i,MD) ret &= (hash_value(l1-1,r1,i) == hash_value(l2-1,r2,i));
        return ret;
    }

    vector<ll> calc(int l, int r){
        vector<ll> ret(MD);
        rep(i,MD) ret[i]=hash_value(l-1,r,i);
        return ret;
    }
};
const vector<ll> RollingHash::hash_base{1009,1021,1013};
const vector<ll> RollingHash::hash_mod{1000000009,1000000007,1000000021};

int main()
{
    string s,t;
    cin >>s >>t;
    RollingHash sh(s), th(t);

    int S = s.size(), T = t.size();
    int ans = 0;
    rep(i,S-T+1)
    {
        int l=0,r=T+1;
        while(r-l>1)
        {
            int m =(l+r)/2;
            if(sh.calc(1+i,1+i+m-1) == th.calc(1,m)) l=m;
            else r=m;
        }

        if(l>=T-1)
        {
            ans += (l==T-1);
            continue;
        }

        ans += (sh.calc(1+i+l+1,i+T) == th.calc(l+2,T));
    }
    cout << ans << endl;
    return 0;
}