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


#define reep(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) reep((i),0,(n))
#define ALL(v) (v).begin(),(v).end()

typedef long long ll;

// 60テ、ツクツ?
const int MAX_N = 6e5 + 1000;


// SA
int n1, k1;
int n2, k2;
int rk1[MAX_N+1];
int sa1[MAX_N+1];
int lcp1[MAX_N+1];
int tmp1[MAX_N+1];

bool compare_sa1(int i, int j) {
	if(rk1[i] != rk1[j]) return rk1[i] < rk1[j];
	else {
		int ri = i + k1 <= n1 ? rk1[i + k1] : -1;
		int rj = j + k1 <= n1 ? rk1[j + k1] : -1;
		return ri < rj;
	}
}

void construct_sa1(string S, int *sa) {
	n1 = S.length();
	for(int i = 0; i <= n1; i++) {
		sa[i] = i;
		rk1[i] = i < n1 ? S[i] : -1;
	}

	for(k1 = 1; k1 <= n1; k1 *= 2) {
		sort(sa, sa + n1 + 1, compare_sa1);
		tmp1[sa[0]] = 0;
		for(int i = 1; i <= n1; i++) {
			tmp1[sa[i]] = tmp1[sa[i-1]] + (compare_sa1(sa[i-1], sa[i]) ? 1 : 0);
		}
		for(int i = 0; i <= n1; i++) {
			rk1[i] = tmp1[i];
		}
	}
}

// LCP
void construct_lcp1(string S, int *sa, int *lcp) {
	int n1 = S.length();
	for(int i = 0; i <= n1; i++)
		rk1[sa[i]] = i;
	int h = 0;
	lcp[0] = 0;
	for(int i = 0; i < n1; i++) {
		int j = sa[rk1[i]-1];
		if(h > 0) h--;
		for(; j + h < n1 && i + h < n1; h++) {
			if(S[j + h] != S[i + h]) break;
		}
		lcp[rk1[i] - 1] = h;
	}
}

int rk2[MAX_N+1];
int sa2[MAX_N+1];
int lcp2[MAX_N+1];
int tmp2[MAX_N+1];

bool compare_sa2(int i, int j) {
	if(rk2[i] != rk2[j]) return rk2[i] < rk2[j];
	else {
		int ri = i + k2 <= n2 ? rk2[i + k2] : -1;
		int rj = j + k2 <= n2 ? rk2[j + k2] : -1;
		return ri < rj;
	}
}

void construct_sa2(string S, int *sa) {
	n2 = S.length();
	for(int i = 0; i <= n2; i++) {
		sa[i] = i;
		rk2[i] = i < n2 ? S[i] : -1;
	}

	for(k2 = 1; k2 <= n2; k2 *= 2) {
		sort(sa, sa + n2 + 1, compare_sa2);
		tmp2[sa[0]] = 0;
		for(int i = 1; i <= n2; i++) {
			tmp2[sa[i]] = tmp2[sa[i-1]] + (compare_sa2(sa[i-1], sa[i]) ? 1 : 0);
		}
		for(int i = 0; i <= n2; i++) {
			rk2[i] = tmp2[i];
		}
	}
}

// LCP
void construct_lcp2(string S, int *sa, int *lcp) {
	int n = S.length();
	for(int i = 0; i <= n; i++)
		rk2[sa[i]] = i;
	int h = 0;
	lcp[0] = 0;
	for(int i = 0; i < n; i++) {
		int j = sa[rk2[i]-1];
		if(h > 0) h--;
		for(; j + h < n && i + h < n; h++) {
			if(S[j + h] != S[i + h]) break;
		}
		lcp[rk2[i] - 1] = h;
	}
}

// RMQ (Segtree)

const int MAX_N_RMQ = 1 << 20;
int n_rmq1, dat1[2 * MAX_N_RMQ - 1];

void init1(int n_) {
	n_rmq1 = 1;
	while(n_rmq1 < n_) n_rmq1 *= 2;
	for(int i = 0; i < 2 * n_rmq1 - 1; i++) {
		dat1[i] = INT_MAX;
	}
}

void update1(int k, int a) {
	k += n_rmq1 - 1;
	dat1[k] = a;
	while(k > 0) {
		k = (k - 1) / 2;
		dat1[k] = min(dat1[k*2 + 1], dat1[k*2 + 2]);
	}
}

int query1(int a, int b, int k, int l, int r) {
	if(r <= a || b <= l) return INT_MAX;
	if(a <= l && r <= b) return dat1[k];
	else {
		int vl = query1(a, b, k * 2 + 1, l, (l+r) / 2);
		int vr = query1(a, b, k * 2 + 2, (l+r) / 2, r);
		return min(vl, vr);
	}
}

int n_rmq2, dat2[2 * MAX_N_RMQ - 1];

void init2(int n_) {
	n_rmq2 = 1;
	while(n_rmq2 < n_) n_rmq2 *= 2;
	for(int i = 0; i < 2 * n_rmq2 - 1; i++) {
		dat2[i] = INT_MAX;
	}
}

void update2(int k, int a) {
	k += n_rmq2 - 1;
	dat2[k] = a;
	while(k > 0) {
		k = (k - 1) / 2;
		dat2[k] = min(dat2[k*2 + 1], dat2[k*2 + 2]);
	}
}

int query2(int a, int b, int k, int l, int r) {
	if(r <= a || b <= l) return INT_MAX;
	if(a <= l && r <= b) return dat2[k];
	else {
		int vl = query2(a, b, k * 2 + 1, l, (l+r) / 2);
		int vr = query2(a, b, k * 2 + 2, (l+r) / 2, r);
		return min(vl, vr);
	}
}

int nn,mm;

int calc_lcp1(int l,int r){
	int ll = min(rk1[l],rk1[r]);
	int rr = max(rk1[l],rk1[r]);
	int ret = query1(ll,rr,0,0,n_rmq1);
	return ret;
}

int calc_lcp2(int l,int r){
	int ll = min(rk2[l],rk2[r]);
	int rr = max(rk2[l],rk2[r]);
	int ret = query2(ll,rr,0,0,n_rmq2);
	return ret;
}

int main(){
	string s;
	string t;
	cin>>s>>t;
	nn = s.size();
	mm = t.size();
	string a = s+'}'+t;
	reverse(ALL(s));
	reverse(ALL(t));
	string b = s+'}'+t;
	init1(nn+mm+1);
	init2(nn+mm+1);
	construct_sa1(a,sa1);
	construct_lcp1(a,sa1,lcp1);
	construct_sa2(b,sa2);
	construct_lcp2(b,sa2,lcp2);
	rep(i,nn+mm+1){
		update1(i,lcp1[i]);
		update2(i,lcp2[i]);
	}
	int ans = 0;
	rep(i,nn+mm+1){
		// cout<<a.substr(sa1[i])<<" "<<lcp1[i]<<" "<<query1(i,i+1,0,0,n_rmq1)<<endl;
	}
	reep(i,15,30){
		// cout<<i<<" "<<dat1[i]<<endl;
	}
	// cout<<n_rmq1<<endl;
	// cout<<a<<endl;
	// cout<<b<<endl;
	rep(i,nn){
		if(i+mm-1>=nn) break;
		int l = calc_lcp1(i,nn+1);
		int r = calc_lcp2(nn-1-(i+mm-1),nn+1);
		// cout<<i<<" "<<nn-1-(i+mm-1)<<endl;
		// cout<<i<<" "<<l<<" "<<r<<endl;
		if(l+r+1==mm) ans++;
	}
	cout<<ans<<endl;
}