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 <iostream>
#include <vector>
#include <random>

#define show(x) cerr << #x << " = " << x << endl

using namespace std;
using ull = unsigned long long;

template <typename S, typename T>
ostream& operator<<(ostream& os, const pair<S, T>& p)
{
    os << "(" << p.first << "," << p.second
       << ")";
    return os;
}


template <typename Container, typename HashType = long long, HashType mod1 = static_cast<HashType>(1000000007), HashType mod2 = static_cast<HashType>(999999937), HashType add1 = static_cast<HashType>(1000010007), HashType add2 = static_cast<HashType>(1003333331)>
class RollingHash
{
public:
    using T = HashType;
    static constexpr HashType MOD1 = mod1;
    static constexpr HashType MOD2 = mod2;
    RollingHash(const Container& original) : size(original.size()), mt{random_device{}()}, base1{getRand1()}, base2{getRand2()}, pow1(size + 1, 1), pow2(size + 1, 1), accum_hash1(size + 1, 0), accum_hash2(size + 1, 0)
    {
        for (int i = 1; i <= size; i++) {
            pow1[i] = (pow1[i - 1] * base1) % mod1;
            accum_hash1[i] = (accum_hash1[i - 1] * base1 + add1 + static_cast<T>(original[i - 1])) % mod1;
        }
        for (int i = 1; i <= size; i++) {
            pow2[i] = (pow2[i - 1] * base2) % mod2;
            accum_hash2[i] = (accum_hash2[i - 1] * base2 + add2 + static_cast<T>(original[i - 1])) % mod2;
        }
    }
    RollingHash(const Container& original, const T base1, const T base2) : size(original.size()), mt{random_device{}()}, base1{base1}, base2{base2}, pow1(size + 1, 1), pow2(size + 1, 1), accum_hash1(size + 1, 0), accum_hash2(size + 1, 0)
    {
        for (int i = 1; i <= size; i++) {
            pow1[i] = (pow1[i - 1] * base1) % mod1;
            accum_hash1[i] = (accum_hash1[i - 1] * base1 + add1 + static_cast<T>(original[i - 1])) % mod1;
        }
        for (int i = 1; i <= size; i++) {
            pow2[i] = (pow2[i - 1] * base2) % mod2;
            accum_hash2[i] = (accum_hash2[i - 1] * base2 + add2 + static_cast<T>(original[i - 1])) % mod2;
        }
    }

    pair<T, T> getHash(const int l, const int r) const  // [l,r)
    {
        const T h1 = (((accum_hash1[r] - accum_hash1[l] * pow1[r - l]) % mod1) + mod1) % mod1;
        const T h2 = (((accum_hash2[r] - accum_hash2[l] * pow2[r - l]) % mod2) + mod2) % mod2;
        return make_pair(h1, h2);
    }

private:
    T getRand1()
    {
        static uniform_int_distribution<T> dist{2, mod1 - 1};
        return dist(mt);
    }
    T getRand2()
    {
        static uniform_int_distribution<T> dist{2, mod2 - 1};
        return dist(mt);
    }

    const int size;
    mt19937 mt;
    const T base1;
    const T base2;
    vector<T> pow1;
    vector<T> pow2;
    vector<T> accum_hash1;
    vector<T> accum_hash2;
};

int main()
{
    string S;
    string T;
    cin >> S >> T;
    const int size = S.size();
    const int len = T.size();
    if (len == 1) {
        int num = 0;
        for (int i = 0; i < size; i++) {
            if (S[i] == T[0]) {
                num++;
            }
        }
        cout << size - num << endl;
        return 0;
    }

    using Type = RollingHash<string>::T;
    using P = pair<Type, Type>;

    mt19937 mt{random_device{}()};
    uniform_int_distribution<Type> dist1{2, RollingHash<string>::MOD1 - 2};
    uniform_int_distribution<Type> dist2{2, RollingHash<string>::MOD2 - 2};
    const Type base1 = dist1(mt);
    const Type base2 = dist2(mt);

    RollingHash<string> s_hash(S, base1, base2);
    RollingHash<string> t_hash(T, base1, base2);

    vector<P> t_left_hash(len);
    vector<P> t_right_hash(len);
    for (int i = 0; i < len; i++) {
        t_left_hash[i] = t_hash.getHash(0, i);
        t_right_hash[i] = t_hash.getHash(i, len);
    }

    int num = 0;
    for (int i = 0; i < size - len + 1; i++) {
        int inf = 0;
        int sup = len;
        while (inf + 1 < sup) {
            const int mid = (inf + sup) / 2;
            if (t_left_hash[mid] == s_hash.getHash(i, i + mid)) {
                inf = mid;
            } else {
                sup = mid;
            }
        }
        const int left = inf;
        inf = 0;
        sup = len;
        while (inf < sup - 1) {
            const int mid = (inf + sup) / 2;
            if (t_right_hash[mid] == s_hash.getHash(i + mid, i + len)) {
                sup = mid;
            } else {
                inf = mid;
            }
        }
        const int right = sup;
        if (right - left == 1) {
            num++;
        }
    }
    cout << num << endl;

    return 0;
}