Задача №111746. Распад галактики

После тысячелетнего правления большей частью Млечного Пути начался окончательный распад КОсмического ОБъединения ОЛигархов на несколько независимых монархий. КОБОЛ является высокоорганизованной империей, которая имеет форму огромного прямоугольного параллепипида n * m * k парсеков. Империя КОБОЛ сильно засекречена, поэтому лишь немногие знают точные значения n, m и k. Для облегчения контроля империя разделена на nmk маленьких владений по одному кубическому парсеку каждое. Эти владения занумерованы следующим образом:

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

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

На вход может подаваться сразу несколько тестов. Первая строка содержит положительное целое число - количество тестов. Первая строка каждого отдельного теста содержит четыре целых числа: n m k l, где n, m и k (1 ≤ n, m, k ≤ 30) — размеры империи, а l — количество независимых монархий, на которое должна распасться империя. Далее следуют l строк с описаниями монархий. Каждая из них имеет следующий вид: p d1 d2 ... dp , где p — количество владений, входящих в монархию (1 ≤ p ≤ 20), а d1, ..., dp — номера этих владений. Монархии перечислены в порядке их отделения от империи.

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

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

Примеры
Входные данные
2
2 2 3 9
2 4 5
3 6 8 10
1 7
1 2
1 11
1 9
1 1
1 0
1 3
2 2 3 3
4 0 1 2 3
4 4 5 6 7
4 8 9 10 11
Выходные данные
4
0
Сдать: для сдачи задач необходимо войти в систему