You are given a board of size $2 \times n$ ($2$ rows, $n$ columns). Some cells of the board contain chips. The chip is represented as '*', and an empty space is represented as '.'. It is guaranteed that there is at least one chip on the board.

In one move, you can choose any chip and move it to any adjacent (by side) cell of the board (if this cell is inside the board). It means that if the chip is in the first row, you can move it left, right or down (but it shouldn't leave the board). Same, if the chip is in the second row, you can move it left, right or up.

If the chip moves to the cell with another chip, the chip in the destination cell disappears (i. e. our chip captures it).

Your task is to calculate the minimum number of moves required to leave exactly one chip on the board.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the board. The second line of the test case contains the string $s_1$ consisting of $n$ characters '*' (chip) and/or '.' (empty cell). The third line of the test case contains the string $s_2$ consisting of $n$ characters '*' (chip) and/or '.' (empty cell).

Additional constraints on the input:

in each test case, there is at least one chip on a board;

the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$).


-----Output-----

For each test case, print one integer — the minimum number of moves required to leave exactly one chip on the board.


-----Examples-----

Input
5
1
*
.
2
.*
**
3
*.*
.*.
4
**.*
**..
5
**...
...**
Output
0
2
3
5
5


-----Note-----

None

Source: codeforces | Difficulty: HARD
Tags: Dynamic programming

Bit manipulation

Greedy algorithms


Solutions:
import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	g = [list(input().rstrip()) for __ in range(2)]
	(left, right) = (-1, 0)
	for i in range(n):
		if g[0][i] == '*' or g[1][i] == '*':
			if left == -1:
				left = i
			right = i
	ret = 0
	f = [0] * (n + 1)
	mid = (left + right) // 2
	for i in range(right):
		if f[i]:
			if g[0][i + 1] == '.' and g[1][i + 1] == '.':
				f[i + 1] = 1
			ret += 1
			continue
		if g[0][i] == '*' and g[1][i] == '*' and (g[0][i + 1] == '.') and (g[1][i + 1] == '.'):
			f[i + 1] = 1
			ret += 2
			continue
		if g[0][i] == '*':
			if g[0][i + 1] == '.' and g[1][i] == '.':
				g[0][i + 1] = '*'
			ret += 1
		if g[1][i] == '*':
			if g[1][i + 1] == '.' and g[0][i] == '.':
				g[1][i + 1] = '*'
			ret += 1
	cnt = 0
	if g[0][right] == '*':
		cnt += 1
	if g[1][right] == '*':
		cnt += 1
	return ret + (1 if cnt == 2 else 0)
for __ in range(int(input())):
	print(solve())


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	board = [input().strip() for _ in range(2)]
	f = 0
	while f < n and board[0][f] == '.' and (board[1][f] == '.'):
		f += 1
	b = n - 1
	while b >= 0 and board[0][b] == '.' and (board[1][b] == '.'):
		b -= 1
	dp = [0, 0]
	for i in range(f, b):
		if board[0][i] == '.' and board[1][i] == '.':
			dp = [min(dp[0] + 1, dp[1] + 2), min(dp[0] + 2, dp[1] + 1)]
		elif board[0][i] == '*' and board[1][i] == '.':
			dp = [min(dp[0] + 1, dp[1] + 2), min(dp[0], dp[1]) + 2]
		elif board[0][i] == '.' and board[1][i] == '*':
			dp = [min(dp[0], dp[1]) + 2, min(dp[0] + 2, dp[1] + 1)]
		else:
			dp = [min(dp[0], dp[1]) + 2, min(dp[0], dp[1]) + 2]
	if board[0][b] == '.' and board[1][b] == '.':
		return min(dp)
	elif board[0][b] == '.' and board[1][b] == '*':
		return min(dp[0] + 1, dp[1])
	elif board[0][b] == '*' and board[1][b] == '.':
		return min(dp[0], dp[1] + 1)
	else:
		return min(dp) + 1
for _ in range(int(input())):
	print(solve())


import sys
input = sys.stdin.readline
t = int(input())
for it in range(t):
	n = int(input())
	a = []
	a.append(list(input()))
	a.append(list(input()))
	for j in range(n):
		if a[0][j] == '*' or a[1][j] == '*':
			l = j
			break
	for j in range(n):
		if a[0][j] == '*' or a[1][j] == '*':
			r = j
	for i in range(l + 1, r + 1):
		if a[0][i - 1] == '*' and a[0][i] == '.' and (a[1][i - 1] == '.'):
			a[0][i] = '*'
		if a[1][i - 1] == '*' and a[1][i] == '.' and (a[0][i - 1] == '.'):
			a[1][i] = '*'
	for i in range(l + 1, r + 1):
		if a[0][i] == '.' and a[0][i - 1] == '*' and (a[1][i] == '.'):
			a[0][i] = '*'
	ans = -1
	for i in a[0]:
		if i == '*':
			ans += 1
	for i in a[1]:
		if i == '*':
			ans += 1
	print(ans)


x = []
for _ in range(int(input())):
	z = int(input())
	s1 = input()
	s2 = input()
	l = r = -1
	for i in range(z):
		if s1[i] == '*' or s2[i] == '*':
			if l == -1:
				l = i
			r = i
	(d1, d2) = (int(s2[l] == '*'), int(s1[l] == '*'))
	for i in range(l + 1, r + 1):
		d3 = min(d1 + 1 + int(s2[i] == '*'), d2 + 2)
		d4 = min(d2 + 1 + int(s1[i] == '*'), d1 + 2)
		(d1, d2) = (d3, d4)
	c = min(d1, d2)
	x.append(c)
[print(i) for i in x]


for p in range(int(input())):
	n = int(input())
	(v, t) = (input(), input())
	l = r = -1
	for i in range(n):
		if v[i] == '*' or t[i] == '*':
			if l == -1:
				l = i
			r = i
	(f, s) = (int(t[l] == '*'), int(v[l] == '*'))
	for i in range(l + 1, r + 1):
		d = min(f + 1 + int(t[i] == '*'), s + 2)
		k = min(s + 1 + int(v[i] == '*'), f + 2)
		(f, s) = (d, k)
	print(min(f, s))


for _ in range(int(input())):
	n = int(input())
	(s1, s2) = (input(), input())
	l = r = -1
	for i in range(n):
		if s1[i] == '*' or s2[i] == '*':
			if l == -1:
				l = i
			r = i
	(dp1, dp2) = (int(s2[l] == '*'), int(s1[l] == '*'))
	for i in range(l + 1, r + 1):
		ndp1 = min(dp1 + 1 + int(s2[i] == '*'), dp2 + 2)
		ndp2 = min(dp2 + 1 + int(s1[i] == '*'), dp1 + 2)
		(dp1, dp2) = (ndp1, ndp2)
	print(min(dp1, dp2))


kvs = int(input())
for _ in range(kvs):
	z = int(input())
	(s1, s2) = (input(), input())
	l = r = -1
	for i in range(z):
		if s1[i] == '*' or s2[i] == '*':
			if l == -1:
				l = i
			r = i
	(d1, d2) = (int(s2[l] == '*'), int(s1[l] == '*'))
	for i in range(l + 1, r + 1):
		d3 = min(d1 + 1 + int(s2[i] == '*'), d2 + 2)
		d4 = min(d2 + 1 + int(s1[i] == '*'), d1 + 2)
		(d1, d2) = (d3, d4)
	print(min(d1, d2))


t = int(input())
for it in range(t):
	n = int(input())
	a = []
	for i in range(2):
		a.append(list(input()))
	for j in range(n):
		if a[0][j] == '*' or a[1][j] == '*':
			l = j
			break
	for j in range(n):
		if a[0][j] == '*' or a[1][j] == '*':
			r = j
	for i in range(l + 1, r + 1):
		if a[0][i - 1] == '*' and a[0][i] == '.' and (a[1][i - 1] == '.'):
			a[0][i] = '*'
		if a[1][i - 1] == '*' and a[1][i] == '.' and (a[0][i - 1] == '.'):
			a[1][i] = '*'
	for i in range(l + 1, r + 1):
		if a[0][i] == '.' and a[0][i - 1] == '*' and (a[1][i] == '.'):
			a[0][i] = '*'
	ans = -1
	for i in range(n):
		if a[0][i] == '*':
			ans += 1
		if a[1][i] == '*':
			ans += 1
	print(ans)