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 <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

//I read this page.
//http://snuke.hatenablog.com/entry/2014/12/03/214243

int T_length,P_length;
char *T,*P,*reverse_T,*reverse_P;

int main(){

	T = new char[3000001];
	reverse_T = new char[3000001];
	scanf("%s",T);

	for(T_length = 0; T[T_length] != '\0'; T_length++);
	for(int i = T_length-1; i >= 0; i--)reverse_T[T_length-1-i] = T[i];
	reverse_T[T_length] = '\0';

	P = new char[3000001];
	reverse_P = new char[3000001];

	scanf("%s",P);

	for(P_length = 0;P[P_length] != '\0';P_length++);
	for(int i = P_length-1; i >= 0; i--)reverse_P[P_length-1-i] = P[i];
	reverse_P[P_length] = '\0';

	int* z_algorithm_P = new int[P_length];

	z_algorithm_P[0] = P_length;
	int index = 1,diff = 0,diff_2;

	while(index < P_length){
		while(index+diff < P_length && P[index+diff] == P[diff])diff++;
		z_algorithm_P[index] = diff;

		if(diff == 0){
			index++;
			continue;
		}else{

			for(diff_2 = 1; diff_2 < diff; diff_2++){
				if(index+diff == P_length || P[index+diff] != P[diff-diff_2]){
					z_algorithm_P[index+diff_2] = min(z_algorithm_P[diff_2],diff-diff_2);
				}else{
					break;
				}
			}

			index += diff_2;
			diff -= diff_2;
		}
	}

	int* z_algorithm_T = new int[T_length];

	index = 0,diff = 0;

	while(index < T_length){
		while(diff < P_length && index+diff < T_length && T[index+diff] == P[diff])diff++;
		z_algorithm_T[index] = diff;

		if(diff == 0){
			index++;
			continue;
		}else{

			for(diff_2 = 1; diff_2 < diff; diff_2++){
				if(diff == P_length || index+diff == T_length || T[index+diff] != P[diff-diff_2]){
					z_algorithm_T[index+diff_2] = min(z_algorithm_P[diff_2],diff-diff_2);
				}else{
					break;
				}
			}

			index += diff_2;
			diff -= diff_2;
		}
	}

	int* reverse_z_algorithm_P = new int[P_length];

	reverse_z_algorithm_P[0] = P_length;
	index = 1,diff = 0;

	while(index < P_length){
		while(index+diff < P_length && reverse_P[index+diff] == reverse_P[diff])diff++;
		reverse_z_algorithm_P[index] = diff;

		if(diff == 0){
			index++;
			continue;
		}else{

			for(diff_2 = 1; diff_2 < diff; diff_2++){
				if(index+diff == P_length || reverse_P[index+diff] != reverse_P[diff-diff_2]){
					reverse_z_algorithm_P[index+diff_2] = min(reverse_z_algorithm_P[diff_2],diff-diff_2);
				}else{
					break;
				}
			}

			index += diff_2;
			diff -= diff_2;
		}
	}

	int* reverse_z_algorithm_T = new int[T_length];
	index = 0,diff = 0;

	while(index < T_length){
		while(diff < P_length && index+diff < T_length && reverse_T[index+diff] == reverse_P[diff])diff++;
		reverse_z_algorithm_T[index] = diff;

		if(diff == 0){
			index++;
			continue;
		}else{

			for(diff_2 = 1; diff_2 < diff; diff_2++){
				if(diff == P_length || index+diff == T_length || reverse_T[index+diff] != reverse_P[diff-diff_2]){
					reverse_z_algorithm_T[index+diff_2] = min(reverse_z_algorithm_P[diff_2],diff-diff_2);
				}else{
					break;
				}
			}

			index += diff_2;
			diff -= diff_2;
		}
	}

	int ans = 0,limit = T_length-P_length;

	for(int i = 0; i <= limit; i++){
		if(z_algorithm_T[i] + reverse_z_algorithm_T[T_length-(P_length+i)] == P_length-1)ans++;
	}

	printf("%d\n",ans);

	return 0;
}