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 <string>
#include <algorithm>
#include <vector>
#include <iostream>
#include <cassert>
using namespace std;

int n, k;
int rk[300100];
int tmp[300100];

bool compare_sa(int i, int j) {
	if(rk[i] != rk[j]) return rk[i] < rk[j];
	int ri, rj;
	ri = i + k <= n ? rk[i+k] : -1;
	rj = j + k <= n ? rk[j+k] : -1;
	return ri < rj;
}

void constract_sa(const string & s, vector<int> & v) {
	v.resize(s.size()+1);
	n = s.size()+1;
	for(int i = 0; i < v.size(); i++)
		v[i] = i;
	for(int i = 0; i < s.size(); i++)
		rk[i] = s[i]+1;
	rk[s.size()] = 0;
	for(k = 1; k <= n; k *= 2) {
		sort(v.begin(), v.end(), compare_sa);
		tmp[v[0]] = 0;
		for(int i = 1; i < v.size(); i++) {
			if(compare_sa(v[i-1], v[i]))
				tmp[v[i]] = tmp[v[i-1]] + 1;
			else
				tmp[v[i]] = tmp[v[i-1]];
		}
		for(int i = 0; i <= n; i++) {
			rk[i] = tmp[i];
		}

	}
}

void construct_lcp(const string & s, const vector<int> & sa, vector<int> & lcp) {
	int n = s.size();
	lcp.resize(n);
	for(int i = 0; i <= n; i++) rk[sa[i]] = i;
	int h = 0;
	lcp[0] = 0;
	for(int i = 0; i < n; i++) {
		assert(rk[i]-1 >= 0);
		int j = sa[rk[i]-1];
		if(h > 0) h--;
		for(; j + h < n && i + h < n; h++) {
			if(s[j+h] != s[i+h]) break;
		}
		lcp[rk[i]-1] = h;
	}
}

int main() {
	string S, T;
	vector<int> sa[2];
	vector<int> same[2];
	cin >> S >> T;

	for(int i = 0; i < 2; i++) {
		int len = 0;
		constract_sa(S, sa[i]);
		same[i].resize(sa[i].size());
		vector<int> lcp;
		construct_lcp(S, sa[i], lcp);
		for(int j = 0; j < sa[i].size(); j++) {
			if(j && lcp[j-1] < len) len = lcp[j-1];
			while(len > 0 && S[sa[i][j]+len-1] != T[len-1])
				len--;
			for(int k = sa[i][j]+len; k < S.size() && len < T.size(); k++) {
				if(S[k] == T[len]) len++;
				else break;
			}
			same[i][sa[i][j]] = len;
		}
		reverse(T.begin(),T.end());
		reverse(S.begin(),S.end());
	}

	/*
	for(int i = 0; i < 2; i++) {
		for(int j = 0; j < sa[i].size(); j++) {
			cout << j << ":" << sa[i][j] << endl;
		} cout << endl;
	}
	for(int i = 0; i < 2; i++) {
		for(int j = 0; j < same[i].size(); j++) {
			cout << same[i][j] << " ";
		} cout << endl;
	}
	// */

	int res = 0;
	for(int i = 0; i < same[0].size(); i++) {
		if(0 <= (int)S.size()-(int)(T.size()+i) && same[0][i] + same[1][S.size()-(T.size()+i)] == T.size()-1) {
			res++;
		}
	}
	cout << res << endl;
}