B. Кодовый замок
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ульяна очень беспокоится за сохранность своих вещей, поэтому пользуется кодовыми замками.

Кодовый замок представляет собой набор из $$$n$$$ роторов, на $$$i$$$-м из которых написаны числа от $$$0$$$ до $$$m_i-1$$$ включительно. Состояние замка определяется массивом чисел $$$a_1, \ldots, a_n$$$ ($$$0 \le a_i \lt m_i$$$) — числа, установленные на каждом из роторов. Изначально все $$$a_i$$$ равны $$$0$$$.

Ульяна установила комбинацию $$$b_1, \ldots, b_n$$$ ($$$0 \le b_i \le m_i - 1$$$) в качестве кода замка. Замок откроется, если в результате манипуляций с замком окажется, что $$$a_i = b_i$$$ для всех $$$i \in \{1,2,\ldots,n\}$$$.

За одно действие Ульяна может выбрать отрезок $$$[l, r]$$$ ($$$1 \le l \le r \le n$$$) и прокрутить все роторы на этом отрезке, после чего для каждого $$$i$$$ ($$$l \le i \le r$$$) значение $$$a_i$$$ заменится на $$$(a_i + 1) \bmod m_i$$$.

Ульяна хочет узнать, насколько быстро она сможет открыть свой замок, в случае необходимости. Помогите ей узнать, какое минимальное количество действий ей для этого потребуется.

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

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

В первой строке каждого набора содержится число $$$n$$$ ($$$1 \le n \le 500$$$) — количество роторов замка.

Во второй строке каждого набора содержатся числа $$$m_1, m_2, \dots, m_n$$$ ($$$2 \leq m_i \leq 500$$$) — количество возможных значений в каждом из роторов.

В третьей строке каждого набора содержатся числа $$$b_1, b_2, \dots, b_n$$$ ($$$0 \leq b_i \le m_i - 1$$$) — комбинация значений, которая разблокирует замок.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$500$$$.

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

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

Пример
Входные данные
3
4
5 5 5 5
1 2 3 4
5
10 2 10 2 10
8 1 8 1 8
7
4 4 3 2 3 4 4
1 3 0 1 0 3 1
Выходные данные
4
10
3
Примечание

Обозначим за $$$[l, r]$$$ действие на отрезке с $$$l$$$ по $$$r$$$.

Первый замок можно открыть за $$$4$$$ последовательных действия: $$$[1, 4], [2, 4], [3, 4], [4, 4]$$$.

Второй замок можно открыть, выполнив $$$8$$$ действий $$$[1, 5]$$$, $$$1$$$ действие $$$[2, 2]$$$ и $$$1$$$ действие $$$[4, 4]$$$.

Третий замок можно открыть, выполнив $$$3$$$ последовательных действия: $$$[1, 7], [2, 6], [2, 6]$$$.