Vus the Cossack has two binary strings, that is, strings that consist only of "0" and "1". We call these strings a and b. It is known that |b| ≤ |a|, that is, the length of b is at most the length of a.

The Cossack considers every substring of length |b| in string a. Let's call this substring c. He matches the corresponding characters in b and c, after which he counts the number of positions where the two strings are different. We call this function f(b, c).

For example, let b = 00110, and c = 11000. In these strings, the first, second, third and fourth positions are different.

Vus the Cossack counts the number of such substrings c such that f(b, c) is even.

For example, let a = 01100010 and b = 00110. a has four substrings of the length |b|: 01100, 11000, 10001, 00010. 

  * f(00110, 01100) = 2;
  * f(00110, 11000) = 4;
  * f(00110, 10001) = 4;
  * f(00110, 00010) = 1.



Since in three substrings, f(b, c) is even, the answer is 3.

Vus can not find the answer for big strings. That is why he is asking you to help him.

Input

The first line contains a binary string a (1 ≤ |a| ≤ 10^6) — the first string.

The second line contains a binary string b (1 ≤ |b| ≤ |a|) — the second string.

Output

Print one number — the answer.

Examples

Input


01100010
00110


Output


3


Input


1010111110
0110


Output


4

Note

The first example is explained in the legend.

In the second example, there are five substrings that satisfy us: 1010, 0101, 1111, 1111.
import java.util.*;
import java.math.*;

// **** C. Vus the Cossack and Strings ****

public class C {
	static char [] in = new char [1000001];
	public static void main (String [] arg) throws Throwable {
		char [] a = next().toCharArray();
		char [] b = next().toCharArray();
		
		int bdiff = 0;
		for (int i = 1; i<b.length; ++i) if (b[i] != b[i-1]) bdiff++;
		boolean flip = bdiff % 2 == 1;
		//System.err.println("FLIP = " + flip);
		
		int ans = 0;
		int N = 0;
		for (int i = 0; i<b.length; ++i) if (a[i] != b[i]) N++;
		N = N % 2;
		if (N == 0) ans++;
		//if (ans == 1) System.err.println("Even at Position 0");
		
		for (int i = 1; i<a.length && i + b.length-1 < a.length; ++i) {
			
			if (flip) N++;
			if (a[i + b.length - 1] != b[b.length-1]) N++;
			if (a[i-1] != b[0]) N++;
			N %= 2;
			if (N == 0) ans++;
			//if (N == 0) System.err.println("Even at position " + i);
		}
		System.out.println(ans);
	}

	
	
	
	
	
	
	
	
	
	
	
	
	
	/************** HELPER CLASSES ***************/
    //static class HS extends HashSet<Integer>{public HS(){super();}public HS(int a){super(a);}};
	//static class AL extends ArrayList<Integer>{public AL(){super();}public AL(int a){super (a);}};
static class Pair implements Comparable<Pair> {int i,j;long L; public Pair(int xx, int yy, long LL){i=xx;j=yy;L=LL;} public int compareTo(Pair p) {
		return (this.L < p.L) ? -1 : ((this.L == p.L && this.i < p.i) ? -1 : 1);}
	}
	
	/************** FAST IO CODE FOLLOWS *****************/
	public static long nextLong() throws Throwable {
		long i = System.in.read();boolean neg = false;while (i < 33) i = System.in.read();if (i == 45) {neg=true;i=48;}i = i - 48;
		int j = System.in.read();while (j > 32) {i*=10;i+=j-48;j = System.in.read();}return (neg) ? -i : i;
	}
	public static int nextInt() throws Throwable {return (int)nextLong();}
	public static String next() throws Throwable {
		int i = 0; while (i < 33 && i != -1) i = System.in.read(); int cptr = 0; while (i >= 33) { in[cptr++] = (char)i; i = System.in.read();}
		return new String(in, 0,cptr);
	}
	/**** LIBRARIES ****/
	public static long gcdL(long a, long b) {while (b != 0) {long tmp = b;b = (a % b);a = tmp;}return a;}
	public static int gcd(int a, int b) {while (b != 0) {int tmp = b;b = (a % b);a = tmp;}return a;}
	public static int[] sieve(int LIM) {
		int i,count = 0;
		boolean [] b = new boolean [LIM];
		for (i = 2;i<LIM; ++i) if (!b[i]) {count++; for (int j = i<<1; j<LIM; j+=i) b[j] = true;}
		int [] primes = new int[count];
		for (i = 2,count=0;i<LIM;++i) if (!b[i]) primes[count++] = i;
		return primes;
	}
	public static int[] numPrimeFactors(int LIM) {
		int i,count = 0;
		int [] b = new int [LIM];
		for (i = 2;i<LIM; ++i) if (b[i] == 0) {count++; for (int j = i; j<LIM; j+=i) b[j]++;}
		return b;
	}
	public static StringBuilder stringFromArray(int [] a) {
		StringBuilder b = new StringBuilder(9*a.length);
		for (int i = 0; i<a.length; ++i) {
			if (i != 0) b = b.append(' ');
			b = b.append(a[i]);
		}
		return b;
	}
}

/* Full Problem Text:
  
Vus the Cossack has two binary strings, that is, strings that consist only of "0" and "1".
We call these strings a and b.
It is known that |b| <q |a|, that is, the length of b is at most the length of a.
The Cossack considers every substring of length |b| in string a.
Let's call this substring c.
He matches the corresponding characters in b and c, after which he counts the number of positions where the two strings are different.
We call this function f(b, c).
For example, let b = 00110, and c = 11000.
In these strings, the first, second, third and fourth positions are different.
Vus the Cossack counts the number of such substrings c such that f(b, c) is even.
For example, let a = 01100010 and b = 00110.
a has four substrings of the length |b|: 01100, 11000, 10001, 00010.


 f(00110, 01100) = 2;
 f(00110, 11000) = 4;
 f(00110, 10001) = 4;
 f(00110, 00010) = 1.
Since in three substrings, f(b, c) is even, the answer is 3.
Vus can not find the answer for big strings.
That is why he is asking you to help him.

 */