E1. Хватит гамать (простая версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Отличие между версиями заключается в том, что в этой версии вам нужно найти только минимальное количество операций. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Вам даны $$$n$$$ массивов, каждый из которых имеет длину $$$m$$$. Обозначим $$$j$$$-й элемент $$$i$$$-го массива как $$$a_{i, j}$$$. Гарантируется, что все $$$a_{i, j}$$$ попарно различны. За одну операцию вы можете сделать следующее:

  • Выбрать какое-то целое число $$$i$$$ ($$$1 \le i \le n$$$) и целое число $$$x$$$ ($$$1 \le x \le 2 \cdot n \cdot m$$$).
  • Для всех целых чисел $$$k$$$ от $$$i$$$ до $$$n$$$ в порядке возрастания сделать следующее:
    1. Добавить элемент $$$x$$$ в начало $$$k$$$-го массива.

    2. Присвоить $$$x$$$ значение, равное последнему элементу в $$$k$$$-м массиве.

    3. Удалить последний элемент из $$$k$$$-го массива.

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

Также вам дано описание массивов, которые необходимо получить после всех операций. То есть после выполнения операций $$$j$$$-й элемент в $$$i$$$-м массиве должен быть равен $$$b_{i, j}$$$. Гарантируется, что все $$$b_{i, j}$$$ попарно различны.

Определите минимальное количество операций, которое необходимо выполнить, чтобы получить нужные массивы.

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 3 \cdot 10^5$$$) — количество массивов и количество элементов в каждом массиве.

$$$i$$$-я из следующих $$$n$$$ строк содержит $$$m$$$ целых чисел $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}$$$ ($$$1 \le a_{i, j} \le 2 \cdot n \cdot m$$$) — элементы в $$$i$$$-м изначальном массиве. Гарантируется, что все $$$a_{i, j}$$$ попарно различны.

$$$i$$$-я из следующих $$$n$$$ строк содержит $$$m$$$ целых чисел $$$b_{i, 1}, b_{i, 2}, \ldots, b_{i, m}$$$ ($$$1 \le b_{i, j} \le 2 \cdot n \cdot m$$$) — элементы в $$$i$$$-м конечном массиве. Гарантируется, что все $$$b_{i, j}$$$ попарно различны.

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

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

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

Пример
Входные данные
4
2 2
2 6
3 4
1 2
7 8
1 5
5 4 1 2 3
5 4 3 2 1
3 3
1 2 3
4 5 6
7 8 9
11 1 2
12 3 4
13 5 6
4 4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 1 2 3
4 18 5 6
7 19 8 20
9 21 22 10
Выходные данные
3
5
3
6
Примечание

В первом наборе входных данных подходит следующая последовательность из $$$3$$$ операций:

  • Применим операцию к первому массиву с $$$x = 1$$$. Тогда в начало первого массива добавится элемент $$$1$$$, а значение $$$x$$$ станет равным $$$6$$$. Последний элемент удалится, и первый массив будет иметь вид $$$[1, 2]$$$. Далее, элемент $$$x$$$ добавляется в начало второго массива, и значение $$$x$$$ становится равным $$$4$$$. Последний элемент второго массива удаляется, и оба массива имеют вид $$$[1, 2]$$$ и $$$[6, 3]$$$ соответственно после первой операции.
  • Применим операцию ко второму массиву с $$$x = 8$$$. Тогда первый массив не изменится, и оба массива будут иметь вид $$$[1, 2]$$$ и $$$[8, 6]$$$ соответственно.
  • Применим операцию ко второму массиву при $$$x = 7$$$, тогда оба массива будут иметь необходимый вид $$$[1, 2]$$$ и $$$[7, 8]$$$ соответственно.

Во втором наборе входных данных получить нужный массив можно только за $$$5$$$ операций.

В третьем наборе входных данных подходит следующая последовательность из $$$3$$$ операций:

  • Применим операцию с $$$x = 11$$$ к первому массиву.
  • Применим операцию с $$$x = 12$$$ ко второму массиву.
  • Применим операцию с $$$x = 13$$$ к третьему массиву.