Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese], and [Bengali] as well.

You are given two binary strings $A$ and $B$ with the same length.

You may perform the following operation any number of times (including zero): pick a substring of $A$ with odd length and invert all the bits (change '0' to '1' or vice versa) at odd positions in this substring. For example, if we choose a substring "01011", we can convert it to "11110" (bits at odd positions are bold).

Determine the minimum number of operations required to change the string $A$ to the string $B$.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single string $A$.
The second line contains a single string $B$.

------  Output ------
For each test case, print a single line containing one integer — the minimum number of operations required.

------  Constraints  ------
$1 ≤ T ≤ 10^{3}$
$1 ≤ |A| = |B| ≤ 10^{5}$
$A$ and $B$ contain only characters '0' and '1'
the sum of $|A|$ over all test cases does not exceed $10^{5}$

----- Sample Input 1 ------ 
3

100001

110111

1010

1010

000

111
----- Sample Output 1 ------ 
2

0

2
----- explanation 1 ------ 
Example case 1: Initially, $A$ is "100001". We choose the substring "000" between the $2$-nd and $4$-th character and convert it to "101".

Now $A$ becomes "110101". We choose the string "0" containing only the $5$-th character and convert it to "1".

Finally, $A$ becomes "110111", which is equal to $B$.

Example case 2: $A$ and $B$ are initially equal, so there is no need to perform any operation.

Difficulty: MEDIUM
Tags: String algorithms

Data structures

Implementation

Greedy algorithms
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	a = input() + '00'
	b = input() + '00'
	b1 = False
	b2 = False
	c = 0
	for i in range(len(a)):
		if i % 2 == 0:
			if int(a[i]) ^ int(b[i]) == 1:
				b1 = True
			else:
				if b1:
					c += 1
				b1 = False
		elif int(a[i]) ^ int(b[i]) == 1:
			b2 = True
		else:
			if b2:
				c += 1
			b2 = False
	print(c)


t = int(input())
for _ in range(t):
	a = input()
	b = input()
	count = 0
	odd = 0
	even = 0
	for i in range(len(a)):
		if a[i] != b[i]:
			if i % 2 == 0 and even == 0:
				count = count + 1
				even = 1
			elif i % 2 != 0 and odd == 0:
				count = count + 1
				odd = 1
		elif i % 2 == 0:
			even = 0
		else:
			odd = 0
	print(count)


T = int(input())
for t in range(T):
	s1 = input()
	s2 = input()
	l = len(s1)
	odd = False
	even = False
	count = 0
	for i in range(l):
		if s1[i] != s2[i]:
			if i % 2 == 0 and even == False:
				count += 1
				even = True
			elif i % 2 != 0 and odd == False:
				count += 1
				odd = True
		elif i % 2 == 0:
			even = False
		else:
			odd = False
	print(count)


for i in range(int(input())):
	a = input() + '00'
	b = input() + '00'
	ans = 0
	for i in range(len(a)):
		if a[i] != b[i]:
			if a[i + 2] == b[i + 2]:
				ans += 1
	print(ans)


for _ in range(int(input())):
	a = int(input(), 2)
	b = int(input(), 2)
	c = a ^ b
	xor = list(bin(c)[2:])
	count = 0
	for i in range(len(xor)):
		if xor[i] == '1':
			count += 1
			while i < len(xor):
				if xor[i] == '0':
					break
				xor[i] = '0'
				i += 2
	print(count)


tests = int(input())
for i in range(tests):
	string1 = input()
	string2 = input()
	length = len(string1)
	is_same = True
	ans = 0
	for j in range(0, length, 2):
		if string1[j] != string2[j]:
			if is_same == True:
				ans += 1
			is_same = False
		else:
			is_same = True
	is_same = True
	for j in range(1, length, 2):
		if string1[j] != string2[j]:
			if is_same == True:
				ans += 1
			is_same = False
		else:
			is_same = True
	print(ans)


def soln(a, b):
	if a == b:
		return 0
	res = 0
	cont = 0
	for i in range(0, len(a), 2):
		if a[i] == b[i]:
			res += cont
			cont = 0
		else:
			cont = 1
	res += cont
	cont = 0
	for i in range(1, len(a), 2):
		if a[i] == b[i]:
			res += cont
			cont = 0
		else:
			cont = 1
	res += cont
	return res
for _ in range(int(input())):
	a = input()
	b = input()
	print(soln(a, b))


for _ in range(int(input())):
	a = input()
	b = input()
	n = len(a)
	x = ''
	for i in range(len(a)):
		if a[i] == b[i]:
			x += '0'
		else:
			x += '1'
	odd = x[0:n:2]
	even = x[1:n:2]
	c = 0
	flag = 0
	for i in range(len(odd)):
		if odd[i] == '1' and flag == 0:
			flag = 1
			c += 1
		elif odd[i] == '0':
			flag = 0
	flag = 0
	for i in range(len(even)):
		if even[i] == '1' and flag == 0:
			flag = 1
			c += 1
		elif even[i] == '0':
			flag = 0
	print(c)


from math import gcd, sqrt, ceil, floor, log10, log2
from heapq import heapify, heappop, heappush, nsmallest, nlargest
from collections import Counter, deque, OrderedDict, defaultdict
from itertools import combinations, permutations, zip_longest
from bisect import bisect_left, bisect_right
from functools import lru_cache, reduce
import sys
import time
import string
import operator
RECURSION_LIMIT = int(10000000.0)
INT_MAX = float('inf')
INT_MIN = float('-inf')
MOD = int(10000000.0) + 9
NEWLINE = '\n'
SPACE = ' '
sys.setrecursionlimit(RECURSION_LIMIT)
inp = lambda fn: fn(input())
inp_vars = lambda fn, delim, convert_to=list: convert_to(map(fn, input().split(delim)))
enum = lambda itr: enumerate(itr)

def toposort(graph, n):
	degree = [0] * n
	for node in graph:
		for adj in graph[node]:
			degree[adj] += 1
	bfs_queue = [node for node in range(n) if not degree[node]]
	for node in bfs_queue:
		for adj in graph[node]:
			degree[adj] -= 1
			if not degree[adj]:
				bfs_queue.append(adj)
	return (bfs_queue, degree)

def dfs(graph, node, visited):
	visited.add(node)
	for adj in graph[node]:
		if adj in visited:
			continue
		dfs(graph, adj, visited)

def solve(*args, **kwargs):
	(a, b) = args
	tmp = ''
	res = 0
	for i in range(len(a)):
		if a[i] == b[i]:
			continue
		res += 1
		j = i
		while j < len(a):
			if a[j] == b[j]:
				break
			if a[j] == '0':
				a[j] = '1'
			else:
				a[j] = '0'
			j += 2
	return res

def main(*args, **kwargs):
	for _ in range(int(input())):
		arg1 = inp(list)
		arg2 = inp(list)
		res = solve(*(arg1, arg2))
		if type(res) in {list, tuple, set}:
			print(*res, sep='\n')
		else:
			print(res)
main()


for _ in range(int(input())):
	a = input()
	b = input()
	temp = []
	for i in range(len(a)):
		temp.append(abs(int(a[i]) - int(b[i])))
	s = 0
	x = temp.count(1)
	for i in range(len(a) - 2):
		if temp[i] == 1 and temp[i + 2] == 1:
			s += 1
	print(x - s)


def solve(a, b):
	n = len(a)
	count = 0
	if a == b:
		return 0
	for i in range(n):
		if a[i] != b[i]:
			a[i] = b[i]
			count += 1
			for j in range(i + 2, n, 2):
				if a[j] != b[j]:
					a[j] = b[j]
				else:
					break
			if a == b:
				return count
t = int(input())
for _ in range(t):
	a = list(str(input()))
	b = list(str(input()))
	print(solve(a, b))


for _ in range(int(input())):
	n = input()
	n1 = input()
	check = 1
	check1 = 1
	ans = 0
	for i in range(0, len(n), 2):
		if n[i] != n1[i] and check == 1:
			ans += 1
			check = 0
		elif n[i] == n1[i]:
			check = 1
	for i in range(1, len(n), 2):
		if n[i] != n1[i] and check1 == 1:
			ans += 1
			check1 = 0
		elif n[i] == n1[i]:
			check1 = 1
	print(ans)


t = int(input())
for _ in range(t):
	s1 = input()
	s2 = input()
	n = len(s1)
	count = 0
	odd = None
	even = None
	for i in range(n):
		if i % 2 == 0:
			if s1[i] != s2[i]:
				even = i
			else:
				if even != None:
					count += 1
				even = None
		elif s1[i] != s2[i]:
			odd = i
		else:
			if odd != None:
				count += 1
			odd = None
	if odd != None:
		count += 1
	if even != None:
		count += 1
	print(count)


for _ in range(int(input())):
	a = input()
	b = input()
	ans = 0
	flag = 0
	for i in range(0, len(a), 2):
		if a[i] != b[i] and flag == 0:
			ans += 1
			flag = 1
		elif a[i] == b[i]:
			flag = 0
	flag = 0
	for i in range(1, len(a), 2):
		if a[i] != b[i] and flag == 0:
			ans += 1
			flag = 1
		elif a[i] == b[i]:
			flag = 0
	print(ans)


def invert(string, char, position):
	if char == '1':
		new_character = '0'
	elif char == '0':
		new_character = '1'
	string = string[:position] + new_character + string[position + 1:]
	return string
for _ in range(int(input())):
	a = input()
	b = input()
	c = 0
	i = 0
	while i < len(a):
		d = 0
		if a[i] != b[i]:
			for j in range(i, len(a), +2):
				if a[j] != b[j]:
					a = invert(a, a[j], j)
					d = d + 1
				else:
					break
			i = i + 1
		else:
			i = i + 1
		if d >= 1:
			c = c + 1
	print(c)


def solve():
	a = input()
	b = input()
	ans = 0
	n = len(a)
	i = 0
	while i < n:
		if a[i] != b[i]:
			while i < n and a[i] != b[i]:
				i += 2
			ans += 1
		i += 2
	i = 1
	while i < n:
		if a[i] != b[i]:
			while i < n and a[i] != b[i]:
				i += 2
			ans += 1
		else:
			i += 2
	print(ans)
for _ in range(int(input())):
	solve()


t = int(input())
for _ in range(t):
	a = input()
	b = input()
	arr = []
	for i in range(len(a)):
		if a[i] == b[i]:
			arr.append(True)
		else:
			arr.append(False)
	mx = 0
	for i in arr:
		if i == False:
			mx += 1
	x = 0
	ans = 0
	while x < len(a) and False in arr:
		while x < len(a) and arr[x]:
			x += 1
		leng = 1
		y = x
		z = x
		while y + 2 < len(a) and arr[y + 2] == False:
			leng += 2
			y += 2
		while x < len(a):
			arr[x] = True
			x += 2
			if x > y:
				ans += 1
				break
		x = z + 1
	print(min(ans, mx))


tsc = int(input())
for i in range(tsc):
	string1 = input()
	string2 = input()
	y = len(string1)
	List = []
	for i in range(0, y):
		a = int(string1[i]) - int(string2[i])
		List.append(abs(a))
	count = List.count(1)
	s = 0
	for i in range(0, y - 2):
		if List[i] == 1 and List[i + 2] == 1:
			s += 1
	print(count - s)


t = int(input())

def count_distinct_groups(a, b, n) -> int:
	i = n
	groups = 0
	while i < len(a):
		if a[i] != b[i]:
			groups += 1
			while i < len(a) and a[i] != b[i]:
				i += 2
		i += 2
	return groups
for i in range(t):
	(a, b) = (input(), input())
	print(count_distinct_groups(a, b, 0) + count_distinct_groups(a, b, 1))


for _ in range(int(input())):
	s1 = list(input())
	s2 = list(input())
	cnt = 0
	for i in range(len(s1)):
		bl = 0
		j = i
		while j < len(s1) and s1[j] != s2[j]:
			s1[j] = s2[j]
			j += 2
			bl = 1
		if bl:
			cnt += 1
	print(cnt)


try:
	for _ in range(int(input())):
		a = input()
		b = input()
		cnt = 0
		i = 0
		while i < len(a):
			if int(a[i]) ^ int(b[i]):
				cnt += 1
				while i < len(a) and int(a[i]) ^ int(b[i]):
					i += 2
			i += 2
		i = 1
		while i < len(a):
			if int(a[i]) ^ int(b[i]):
				cnt += 1
				while i < len(a) and int(a[i]) ^ int(b[i]):
					i += 2
			i += 2
		print(cnt)
except:
	pass


for _ in range(int(input())):
	a = input()
	b = input()
	l = len(a)
	ans = 0
	i = 0
	while i < l:
		if a[i] != b[i]:
			while i < l:
				if a[i] == b[i]:
					break
				i += 2
			ans += 1
		else:
			i += 2
	i = 1
	while i < l:
		if a[i] != b[i]:
			while i < l:
				if a[i] == b[i]:
					break
				i += 2
			ans += 1
		else:
			i += 2
	print(ans)


for _ in range(int(input())):
	a = str(input())
	b = str(input())
	ali = list(a)
	bli = list(b)
	fnd = False
	ans = 0
	for i in range(0, len(ali), 2):
		if ali[i] != bli[i]:
			fnd = True
		elif fnd:
			ans += 1
			fnd = False
	if fnd:
		ans += 1
		fnd = False
	for i in range(1, len(ali), 2):
		if ali[i] != bli[i]:
			fnd = True
		elif fnd:
			ans += 1
			fnd = False
	if fnd:
		ans += 1
		fnd = False
	print(ans)


T = int(input())
for tj in range(T):
	s = input()
	t = input()
	if s == t:
		print(0)
		continue
	else:
		k = []
		for i in range(len(s)):
			if s[i] != t[i]:
				k.append(1)
			else:
				k.append(0)
	coun = 0
	for i in range(len(k)):
		if k[i] == 1:
			k[i] = 0
			coun += 1
			if i + 2 < len(k):
				for j in range(i + 2, len(k), 2):
					if k[j] == 1:
						k[j] = 0
					else:
						break
	print(coun)


for _ in range(int(input())):
	a = input()
	b = input()
	n = len(a)
	f = False
	cnt = 0
	for i in range(0, n, 2):
		if a[i] != b[i]:
			f = True
		elif f:
			cnt += 1
			f = False
	if f:
		cnt += 1
		f = False
	f = False
	for i in range(1, n, 2):
		if a[i] != b[i]:
			f = True
		elif f:
			cnt += 1
			f = False
	if f:
		cnt += 1
		f = False
	print(cnt)


def solve(a, b):
	res = []
	(iseven, isodd) = (False, False)
	for i in range(len(a)):
		if a[i] != b[i]:
			res.append(i)
		if i % 2 == 0:
			iseven = True
		if i % 2 != 0:
			isodd = True
	if len(res) == 0:
		print(0)
		return
	a_even = []
	a_odd = []
	for i in res:
		if i % 2 == 0:
			a_even.append(i)
		else:
			a_odd.append(i)
	curr = -1
	count = 0
	for i in range(len(a_even)):
		if curr == -1:
			curr = a_even[i]
			count += 1
		elif curr + 2 == a_even[i]:
			curr = a_even[i]
		else:
			curr = a_even[i]
			count += 1
	curr = -1
	for i in range(len(a_odd)):
		if curr == -1:
			curr = a_odd[i]
			count += 1
		elif curr + 2 == a_odd[i]:
			curr = a_odd[i]
		else:
			curr = a_odd[i]
			count += 1
	print(count)
t = int(input())
for i in range(t):
	a = input()
	b = input()
	solve(a, b)


T = int(input())
for jj in range(T):
	A = input()
	B = input()
	Ln = len(A)
	(q1, q2) = (-1, -1)
	tm = 0
	(r1, r2) = (0, 0)
	for i in range(Ln):
		(a, b) = (A[i], B[i])
		if a != b:
			if i % 2:
				if q1 == -1:
					q1 = i
					r1 = 1
				elif i - q1 == 2:
					q1 = i
				else:
					q1 = i
					tm += 1
			elif q2 == -1:
				q2 = i
				r2 = 1
			elif i - q2 == 2:
				q2 = i
			else:
				tm += 1
				q2 = i
	print(tm + r1 + r2)


for _ in range(int(input())):
	a = input()
	b = input()
	e = []
	o = []
	for i in range(len(a)):
		if a[i] != b[i]:
			if (i + 1) % 2 == 0:
				e.append(i)
			else:
				o.append(i)
	a = 0
	for i in range(len(e) - 1):
		if e[i + 1] - e[i] > 2:
			a = a + 1
	if len(e) != 0:
		a = a + 1
	for i in range(len(o) - 1):
		if o[i + 1] - o[i] > 2:
			a = a + 1
	if len(o) != 0:
		a = a + 1
	print(a)


mod = 1000000007
from math import factorial, ceil, pow, sqrt, floor
from sys import stdin, stdout
from collections import defaultdict, Counter, deque
for _ in range(int(stdin.readline())):
	a = list(stdin.readline().strip('\n'))
	b = list(stdin.readline().strip('\n'))
	(ans, n, c, i) = (0, len(a), 0, 0)
	while i < n:
		if a[i] != b[i]:
			j = i
			while j < n and a[j] != b[j]:
				b[j] = a[j]
				j += 2
			ans += 1
		i += 1
	print(ans)


def atoB():
	t = int(input())
	for _ in range(t):
		a = list(input())
		b = list(input())
		n = len(a)
		ans = 0
		for i in range(n):
			if a[i] != b[i]:
				p = i
				while p < n and a[p] != b[p]:
					a[p] = b[p]
					p += 2
				ans += 1
		print(ans)
atoB()


for _ in range(int(input())):
	a = list(input())
	b = list(input())
	c = 0
	i = 0
	while i < len(a):
		if a[i] != b[i]:
			j = i
			while j < len(a) and a[j] != b[j]:
				a[j] = b[j]
				j += 2
			c += 1
		i += 1
	print(c)


import sys
for i in range(int(input())):
	x = input()
	y = input()
	a = []
	for i in x:
		a.append(i)
	b = []
	for i in y:
		b.append(i)
	c = 0
	for i in range(len(a)):
		if a[i] == b[i]:
			continue
		p = i
		while p < len(a) and a[p] != b[p]:
			a[p] = b[p]
			p = p + 2
		c = c + 1
	print(c)


for i in range(int(input())):
	a = list(input())
	b = list(input())
	c = 0
	while len(a) > 0:
		if a[0] == b[0]:
			a.pop(0)
			b.pop(0)
		else:
			c += 1
			for i in range(0, len(a), 2):
				if a[i] == b[i]:
					break
				else:
					a[i] = b[i]
	print(c)


from collections import deque
for _ in range(int(input())):
	a = deque(input())
	b = deque(input())
	count = 0
	while len(a) > 0:
		if a[0] == b[0]:
			a.popleft()
			b.popleft()
		else:
			count += 1
			for i in range(0, len(a), 2):
				if a[i] == b[i]:
					break
				else:
					a[i] = b[i]
	print(count)


for _ in range(int(input())):
	s = input()
	s1 = input()
	c = 0
	for i in range(len(s)):
		if s[i] != s1[i]:
			j = i
			while s[j] != s1[j] and j < len(s):
				s = s[:j] + s1[j] + s[j + 1:]
				j = j + 2
				if j >= len(s):
					break
			c = c + 1
	print(c)


import sys
ins = lambda : sys.stdin.readline().strip()
inarr = lambda s: list(map(s, sys.stdin.readline().strip().split()))
outs = lambda n: sys.stdout.write(str(n) + '\n')
outarr = lambda li: sys.stdout.write(' '.join(map(str, li)) + '\n')
gcd = lambda a, b: b if a == 0 else gcd(b % a, a)

def solve(a, b):
	n = len(a)
	ans = 0
	for i in range(n):
		if a[i] == b[i]:
			pass
		else:
			j = i
			while j < n and a[j] != b[j]:
				a[j] = b[j]
				j += 2
			ans += 1
	outs(ans)
	return
t = int(ins())
for _ in range(t):
	a = ins()
	b = ins()
	a = list(a)
	b = list(b)
	solve(a, b)


try:
	for _ in range(int(input())):
		A = input()
		B = input()
		count = 0
		i = 0
		while i < len(A):
			if A[i] != B[i]:
				while i < len(A) and A[i] != B[i]:
					i += 2
				count += 1
			i = i + 2
		i = 1
		while i < len(A):
			if A[i] != B[i]:
				while i < len(A) and A[i] != B[i]:
					i = i + 2
				count += 1
			i = i + 2
		print(count)
except:
	exit(0)


try:
	for _ in range(int(input())):
		a = [int(i) for i in input()]
		b = [int(i) for i in input()]
		n = len(a)
		i = 0
		ans = 0
		for y in range(2):
			t = 0
			while i <= n - 1:
				if a[i] == b[i] and t > 0:
					ans += 1
					t = 0
				t += 1
				if a[i] == b[i] and t == 1:
					t = 0
				i += 2
			if t > 0:
				ans += 1
			i = 1
		print(ans)
except:
	pass


for _ in range(int(input())):
	a = input()
	b = input()
	n = len(a)
	if a == b:
		print(0)
	else:
		(s, i) = (0, 0)
		while i < n:
			if a[i] != b[i]:
				while i < n and a[i] != b[i]:
					i += 2
				s += 1
			i += 2
		i = 1
		while i < n:
			if a[i] != b[i]:
				while i < n and a[i] != b[i]:
					i += 2
				s += 1
			i += 2
		print(s)


t = int(input())
for _ in range(t):
	a = list(input())
	b = list(input())
	count = 0
	while len(a) > 0:
		if a[0] == b[0]:
			a.pop(0)
			b.pop(0)
		else:
			count += 1
			for i in range(0, len(a), 2):
				if a[i] == b[i]:
					break
				else:
					a[i] = b[i]
	print(count)


t = int(input())
for _ in range(0, t):
	a = input()
	b = input()
	m = len(a)
	cnt = 0
	i = 0
	while i < m:
		if a[i] != b[i]:
			cnt += 1
			while i + 2 < m and a[i + 2] != b[i + 2]:
				i += 2
		i += 2
	i = 1
	while i < m:
		if a[i] != b[i]:
			cnt += 1
			while i + 2 < m and a[i + 2] != b[i + 2]:
				i += 2
		i += 2
	print(cnt)


for _ in range(int(input())):
	s = list(input())
	k = list(input())
	count = 0
	while len(s) > 0:
		if s[0] == k[0]:
			s.pop(0)
			k.pop(0)
		else:
			count += 1
			for i in range(0, len(s), 2):
				if s[i] == k[i]:
					break
				else:
					s[i] = k[i]
	print(count)


try:
	t = int(input())
	for i in range(0, t):
		a = input()
		b = input()
		(o1, e1) = ('', '')
		(o2, e2) = ('', '')
		(s1, s2) = (0, 0)
		for i in range(0, len(a)):
			if i % 2 == 0:
				o1 += a[i]
				o2 += b[i]
			else:
				e1 += a[i]
				e2 += b[i]
		(op1, op2) = ('', '')
		for i in range(0, len(o1)):
			if o1[i] != o2[i]:
				op1 += '1'
			else:
				op1 += '0'
		from itertools import groupby
		q = [(len(list(c)), str(k)) for (k, c) in groupby(op1)]
		for i in range(0, len(q)):
			if q[i][1] == '1':
				s1 += 1
		for i in range(0, len(e1)):
			if e1[i] != e2[i]:
				op2 += '1'
			else:
				op2 += '0'
		from itertools import groupby
		q1 = [(len(list(c)), str(k)) for (k, c) in groupby(op2)]
		for i in range(0, len(q1)):
			if q1[i][1] == '1':
				s2 += 1
		print(s1 + s2)
except:
	pass


for _ in range(int(input())):
	a = input()
	b = input()
	n = len(a)
	even_lis = []
	odd_lis = []
	for i in range(n):
		if i % 2 == 0:
			if a[i] == b[i]:
				even_lis.append(0)
			else:
				even_lis.append(1)
		elif a[i] == b[i]:
			odd_lis.append(0)
		else:
			odd_lis.append(1)
	count = 0
	if 1 in even_lis:
		init_i = even_lis.index(1)
		flag = 1
		for i in range(init_i, len(even_lis)):
			if even_lis[i] == 0 and flag == 1:
				count += 1
				flag = 0
			elif even_lis[i] == 1 and flag == 0:
				flag = 1
		if even_lis[-1] == 1:
			count += 1
	even_lis = odd_lis[:]
	if 1 in even_lis:
		init_i = even_lis.index(1)
		flag = 1
		for i in range(init_i, len(even_lis)):
			if even_lis[i] == 0 and flag == 1:
				count += 1
				flag = 0
			elif even_lis[i] == 1 and flag == 0:
				flag = 1
		if even_lis[-1] == 1:
			count += 1
	print(count)


for i in range(int(input())):
	flag = 0
	n = list(input())
	k = list(input())
	for i in range(len(n)):
		if n[i] == k[i]:
			continue
		else:
			flag = flag + 1
			j = i
			while j < len(n) and n[j] != k[j]:
				n[j] = k[j]
				if j + 2 < len(n) and n[j + 2] != k[j + 2]:
					j += 2
				else:
					break
	if flag == 0:
		print(flag)
		continue
	print(flag)


def check(A, B):
	ans = i = 0
	while i < len(A):
		if A[i] != B[i]:
			while i < len(A) and A[i] != B[i]:
				i += 2
			ans += 1
		i += 2
	i = 1
	while i < len(A):
		if A[i] != B[i]:
			while i < len(A) and A[i] != B[i]:
				i += 2
			ans += 1
		i += 2
	return ans
T = int(input())
for i in range(T):
	(A, B) = (input().strip(), input().strip())
	print(check(A, B))


def arrIn():
	return list(map(int, input().split()))

def mapIn():
	return map(int, input().split())
for tests in range(int(input())):
	a = input()
	b = input()
	n = len(a)
	c = 0
	c1 = 0
	for i in range(1, n, 2):
		if a[i] == b[i]:
			c += c1
			c1 = 0
		else:
			c1 = 1
	c += c1
	c1 = 0
	for i in range(0, n, 2):
		if a[i] == b[i]:
			c += c1
			c1 = 0
		else:
			c1 = 1
	c += c1
	print(c)


t = int(input())
for _ in range(t):
	a = input()
	b = input()
	x = []
	for i in range(len(a)):
		if a[i] != b[i]:
			x.append(i + 1)
	if x:
		ans = 0
		v = {i: 0 for i in x}
		for i in x:
			if v[i] == 0:
				while i in v:
					v[i] = 1
					i += 2
				ans += 1
		print(ans)
	else:
		print(0)


for _ in range(int(input())):
	a = input()
	b = input()
	aEven = ''
	bEven = ''
	aOdd = ''
	bOdd = ''
	for i in range(len(a)):
		if i % 2 == 0:
			aOdd += a[i]
			bOdd += b[i]
		else:
			aEven += a[i]
			bEven += b[i]
	count = 0
	switch = False
	for i in range(len(aEven)):
		if aEven[i] != bEven[i]:
			switch = True
		else:
			if switch == True:
				count += 1
			switch = False
	if switch == True:
		count += 1
	switch = False
	for i in range(len(aOdd)):
		if aOdd[i] != bOdd[i]:
			switch = True
		else:
			if switch == True:
				count += 1
			switch = False
	if switch == True:
		count += 1
	print(count)


for _ in range(int(input())):
	a = input()
	b = input()
	i = 0
	count = 0
	while i < len(a):
		if a[i] != b[i]:
			while i < len(a) and a[i] != b[i]:
				i += 2
			count += 1
		i += 2
	i = 1
	while i < len(a):
		if a[i] != b[i]:
			while i < len(a) and a[i] != b[i]:
				i += 2
			count += 1
		i += 2
	print(count)


for _ in range(int(input())):
	a = input()
	b = input()
	a__even = ''
	a__odd = ''
	b__even = ''
	b__odd = ''
	for i in range(len(a)):
		if i % 2 == 1:
			a__even += a[i]
			b__even += b[i]
		else:
			a__odd += a[i]
			b__odd += b[i]
	cnt = 0
	j = 0
	for i in range(len(a__even)):
		if a__even[i] != b__even[i]:
			j += 1
		else:
			if j > 0:
				cnt += 1
			j = 0
	if j > 0:
		cnt += 1
	j = 0
	for i in range(len(a__odd)):
		if a__odd[i] != b__odd[i]:
			j += 1
		else:
			if j > 0:
				cnt += 1
			j = 0
	if j > 0:
		cnt += 1
	print(cnt)


t = int(input())
output = []
for _ in range(t):
	a = list(map(int, input()))
	b = list(map(int, input()))
	if a == b:
		output.append('0')
	else:
		indices = []
		for (index, (num1, num2)) in enumerate(zip(a, b)):
			if num1 != num2:
				indices.append(index + 1)
		count = 0
		while indices:
			curr = indices[0]
			while True:
				if curr in indices:
					indices.remove(curr)
					curr += 2
				else:
					break
			count += 1
		output.append(str(count))
print('\n'.join(output))