Обучение в Ягеллонском университете в Кракове имеет свои плюсы и минусы. Плюсы: Ягеллонский университет. Минусы: Краков... Точнее, постоянная необходимость заниматься реконструкцией трамвайных путей.

Изначально сеть общественного транспорта состоит из некоторого количества трамвайных линий. Потом одну из них приостанавливают, затем другую, потом еще... Как Вы сами знаете, в Кракове существует нерушимое правило: всегда приостанавливать линию до того, как возобновит работу какая-либо из ранее приостановленных линий. Сейчас еще не все линии приостановлены (пока), и вы сидите в трамвае, раздражаясь, что ваше прямое сообщение с университетом только что исчезло. Смотришь в окно и спрашиваешь себя: "Я действительно самый невезучий пассажир в этом городе? Или где-то есть кто-то, кому нужно пересаживаться еще большее число раз, чтобы добраться туда, куда он хочет?"

Точнее, мы говорим, что остановка B достижима из остановки A с c изменениями, если существуют такие линии l0, ..., lc что l0 обслуживает остановку A, lc обслуживает остановку B, и для каждого 0 ≤ i < c существует существует некоторая остановка, обслуживаемая li и li+1. В каждый момент времени Вы хотите знать наибольшее значение c, при котором существует такая пара остановок (A, B), что в B можно добраться из A с c изменениями, но при этом B недостижима из A с c' изменениями для любого c' < c.

Обратите внимание, что иногда вообще невозможно проехать между парой остановок. Как следует из приведенного выше определения, Вы решаете не учитывать такие пары в своем анализе - если кто-то захочет проехать между этими остановками, он воспользуется Uber.

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

Первая строка содержит количество тестов z (1 ≤ z ≤ 35). Далее следует описание тестов.

Первая строка каждого теста содержит количество остановок n и количество трамвайных путей k (2 ≤ n, k ≤ 750).

Остановки пронумерованы от 1 до n, а линии пронумерованы от 1 до k.

Затем следуют k строк. i-я из этих строк описывает маршрут трамвайной линии номер i. Каждая строка начинается с целого числа ri (2 ≤ ri ≤ n), за которым следуют ri различных целых чисел ai,j (1 ≤ ai,j ≤ n) - идентификаторы остановок, обслуживаемых i-ым трамвайным маршрутом. Любая трамвайная линия идет в обоих направлениях.

Следующая строка содержит одно целое число s (1 ≤ s ≤ k − 1).

Затем следуют s строк, описывающих порядок остановки трамвайных путей. Каждая из этих строк содержит единственное целое число si (1 ≤ si ≤ k) - идентификатор остановленной линии трамвая. Любая линия может быть приостановлена не более одного раза.

Суммы значений n и k во всех тестах не превышают 1000 каждое.

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

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

Примечание

Первоначально для проезда, например, от остановки 4 до остановки 5 (или наоборот) требуется одна пересадка. Такой проезд возможен по маршруту 2, затем по маршруту 1. Нет пар остановок, требующих 2 или более пересадки.

После удаления линии 1 для проезда от остановки 1 до остановки 3 (или наоборот) требуется две пересадки.

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

После удаления линий 1, 4 и 3 единственная пара остановок, достижимая друг от друга, - это (1, 4). Для проезда между этими остановками не требуется никаких пересадок.