F. Несправедливая бинарная жизнь
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Юрию даны две бинарные строки $$$a$$$ и $$$b$$$, длина каждой из которых равна $$$n$$$. Эти две строки динамически определяют сетку размером $$$n \times n$$$. Пусть $$$(i, j)$$$ обозначает ячейку в $$$i$$$-й строке и $$$j$$$-м столбце. Начальное значение ячейки $$$(i, j)$$$ равно $$$a_i \oplus b_j$$$, где $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ. .

Путешествие Юрия всегда начинается с ячейки $$$(1, 1)$$$. Из ячейки $$$(i, j)$$$ он может перемещаться только вниз в $$$(i + 1, j)$$$ или вправо в $$$(i, j + 1)$$$. Его путешествие возможно, если существует допустимый путь, по которому все ячейки на пути, включая $$$(1, 1)$$$, имеют значение 0.

Перед отправлением он может выполнить следующую операцию любое количество раз:

  • Выбрать один индекс $$$1 \le i \le n$$$ и изменить значение либо $$$a_i$$$, либо $$$b_i$$$ ($$$0$$$ становится $$$1$$$, а $$$1$$$ становится $$$0$$$). Сетка также изменится соответственно.

Пусть $$$f(x, y)$$$ обозначает минимальное количество необходимых операций, чтобы Юрий мог добраться до ячейки $$$(x,y)$$$. Вам необходимо определить сумму $$$f(x, y)$$$ для всех $$$1 \leq x, y \leq n$$$.

Обратите внимание, что каждый из этих $$$n^2$$$ случаев независим, что означает, что вам нужно предполагать, что сетка находится в своем исходном состоянии в каждом случае (т.е. фактические операции не выполняются).

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

Вторая строка каждого набора содержит бинарную строку $$$a$$$ ($$$|a| = n$$$, $$$a_i \in \{0, 1\}$$$).

Третья строка каждого набора содержит бинарную строку $$$b$$$ ($$$|b| = n$$$, $$$b_i \in \{0, 1\}$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — сумму минимальных операций для всех возможных ячеек.

Пример
Входные данные
3
2
11
00
2
01
01
4
1010
1101
Выходные данные
5
4
24
Примечание

В первом примере показана сетка $$$2 \times 2$$$.

$$$$$$ 11 \\ 11 $$$$$$

В исходном состоянии Юрий не может добраться ни до одной ячейки.

Юрий может изменить $$$a_1$$$, чтобы сетка стала:

$$$$$$ 00 \\ 11 $$$$$$

и Юрий может перемещаться к ячейкам $$$(1,1)$$$ и $$$(1,2)$$$.

С другой стороны, Юрий может изменить $$$b_1$$$, чтобы сетка стала:

$$$$$$ 01 \\ 01 $$$$$$

и Юрий может перемещаться к ячейкам $$$(1,1)$$$ и $$$(2,1)$$$.

Чтобы добраться до ячейки $$$(2,2)$$$, можно показать, что ему необходимо выполнить как минимум две операции. Например, он может изменить как $$$a_1$$$, так и $$$a_2$$$, чтобы сетка стала:

$$$$$$ 00 \\ 00 $$$$$$

Таким образом, ответ равен $$$1+1+1+2=5$$$.