В алгоритмах поиска мы часто сталкиваемся со следующей задачей: имеется множество текстовых записей и последовательность ключевых слов, и требуется найти записи, соответствующие этим ключевым словам. Например, запись «2025 China Collegiate Programming Contest (CCPC) Jinan Regional Contest» соответствует ключевым словам «2025 CCPC Jinan». Обратите внимание, что последовательность ключевых слов не обязательно должна идти в записи подряд; достаточно того, чтобы она встречалась в записи как подпоследовательность.

Исходя из практических соображений, мы можем определить следующий алгоритм релевантности: выберем из записи как можно больше непересекающихся подпоследовательностей так, чтобы каждая выбранная подпоследовательность в точности совпадала с заданной последовательностью ключевых слов; тогда релевантностью называется количество выбранных подпоследовательностей.

В этой задаче каждое слово можно представить положительным целым числом. Дана последовательность ключевых слов длины $m$; для упрощения задачи все ключевые слова попарно различны. Кроме того, даны $n$ записей, где $i$-я запись представляет собой последовательность положительных целых чисел длины $l_i$. Ваша цель — вычислить релевантность каждой записи.

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

Первая строка входных данных содержит целое число $m$ ($1 \le m \le 10$), обозначающее длину последовательности ключевых слов.

Следующая строка содержит $m$ целых чисел $b_1, b_2, \dots, b_m$ ($1 \le b_i \le m$), представляющих последовательность ключевых слов. Гарантируется, что все $b_1, b_2, \dots, b_m$ попарно различны.

Следующая строка содержит целое число $n$ ($1 \le n \le 100$), обозначающее количество записей.

В следующих $n$ строках: в $i$-й строке сначала записано целое число $l_i$ ($1 \le l_i \le 10^6$), обозначающее длину $i$-й записи, а затем $l_i$ целых чисел $a_{i,1}, a_{i,2}, \dots, a_{i,l_i}$ ($1 \le a_{i,j} \le 10^6$), представляющих содержимое $i$-й записи.

Гарантируется, что суммарная длина всех записей не превосходит $10^6$.

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

Выведите $n$ строк, где $i$-я строка содержит одно целое число — релевантность $i$-й записи.

Пример

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

4
4 2 1 3
3
8 4 2 1 3 4 2 3 1
9 1 4 2 4 1 2 1 3 3
12 1 1 2 3 4 2 1 1 2 1 3 3

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

1
2
1

Примечание

Ниже для обозначения подпоследовательностей используются последовательности индексов.

• Для первой записи можно выбрать $[1, 2, 3, 7]$ в качестве подпоследовательности; тогда $[a_1, a_2, a_3, a_7] = [4, 2, 1, 3]$, что в точности совпадает с последовательностью ключевых слов.
• Для второй записи можно выбрать $[2, 3, 5, 9]$ и $[4, 6, 7, 8]$ в качестве подпоследовательностей. Обратите внимание, что $[2, 3, 7, 9]$ и $[4, 6, 7, 9]$ нельзя выбрать одновременно, так как их позиции пересекаются.