402801: GYM100885 B Железная дорога

На сайте Берляндских Железных Дорог (БЖД) любой может купить билет. Для этого ему лишь нужно заполнить несложную форму, а затем пройти еще несколько простых шагов. Руководство БЖД недавно задумалось о том, насколько легко людям использовать эту форму, и поручило вам провести измерения, чтобы оптимизировать количество действий, нужных для заполнения формы.

Форма состоит из двух полей: станция отправления и станция назначения. Когда человек заходит на сайт, в этих полях уже введены станции — те, которые сайт считает наиболее вероятными. Также под каждым полем есть список названий некоторых, самых популярных, станций — клик по элементу списка подставляет название станции в соответствующее поле. Наконец, есть кнопка «Поменять местами станцию отправления и станцию назначения». Кроме того, конечно, пользователь также волен ввести названия нужных ему станций вручную. К сожалению, из-за ошибки в коде сайта, редактировать введенное или выбранное название нельзя, можно только ввести его заново.

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

Вам нужно написать программу, которая по желаемым станциям отправления и назначения и начальному виду страницы (введенные станции, список популярных станций) определит минимальное количество очков действия, необходимое для того, чтобы ввести желаемые станции в соответствующие поля ввода.

В первой строке входного файла записано количество тестов в этом файле — единственное целое число K(1 ≤ K ≤ 10). В последующих строках записаны K тестов.

Каждый отдельный тест состоит из нескольких строк. В первой строке теста записано название желаемой станции отправления. Во второй строке — название желаемой станции назначения. Гарантируется, что желаемая станция отправления не совпадает с желаемой станцией назначения.

В третьей строке — текущее введенное название станции отправления. В четвертой строке — текущее введенное название станции назначения.

В пятой строке — одно целое число N(0 ≤ N ≤ 100) — количество популярных вариантов станции отправления. В следующих N строках записаны эти варианты, по одному на строке. Все варианты различны.

После этого записано количество популярных вариантов станции назначения — одно целое число M(0 ≤ M ≤ 100). В следующих M строках записаны эти варианты, по одному на строке. Все варианты различны.

Названия станций могут состоять из больших и маленьких латинских букв, пробелов и дефисов. Длина каждого названия не превышает 100 символов. Названия станций всегда начинаются и заканчиваются буквой. Любой пробел или дефис обязательно окружен буквами.

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

2
Nizhny Novgorod
Moskva
Samara
Petrozavodsk
2
Arkhangelsk
Nizhny Novgorod
2
Moskva
Samara
Moskva
Nizhny Novgorod
Sankt-Petersburg
Petrozavodsk
2
Arkhangelsk
Ulyanovsk
2
Volgograd
Samara

2
21

1
Moskva
Nizhny Novgorod
Nizhny Novgorod
Moskva
3
Arkhangelsk
Ulyanovsk
Kazan
3
Volgograd
Kazan
Samara

1

Первый пример состоит из двух тестов. В первом тесте пользователю достаточно кликнуть по Nizhny Novgorod в списке популярных станций отправления, чтобы заменить Samara на желаемую станцию отправления, а затем кликнуть по Moskva в списке популярных станций назначения, чтобы заменить Petrozavodsk на желаемую станцию. Два клика требуют двух очков действия.

Во втором тесте у пользователя нет выбора, кроме как ввести названия станций вручную. Ввод Moskva потребует 6 очков действий, а ввод Nizhny Novgorod — 15 очков. В сумме требуется 21 очко.

Второй пример стоит из единственного теста. В этом тесте пользователю достаточно сначала кликнуть по Nizhny Novgorod в списке популярных станций отправления, а затем нажать на кнопку «Поменять местами станцию отправления и станцию назначения». На это потребуется два очка.

Иллюстрация ко второму примеру: