Negli algoritmi di ricerca incontriamo spesso il seguente problema: ci sono molte voci e una sequenza di parole chiave, e si vogliono trovare le voci che corrispondono alle parole chiave. Ad esempio, la voce "2025 China Collegiate Programming Contest (CCPC) Jinan Regional Contest" corrisponde alle parole chiave "2025 CCPC Jinan". Si noti che la sequenza di parole chiave non deve necessariamente apparire consecutivamente nella voce; è sufficiente che appaia come sottosequenza della voce.

Sulla base di considerazioni pratiche, possiamo definire il seguente algoritmo di rilevanza: selezionare dalla voce il maggior numero possibile di sottosequenze non sovrapposte, in modo che ciascuna sottosequenza sia esattamente uguale alla sequenza di parole chiave data; la rilevanza è quindi il numero di sottosequenze selezionate.

In questo problema, ogni parola può essere rappresentata da un intero positivo. Data una sequenza di parole chiave di lunghezza $m$, per semplificare il problema le parole chiave sono tutte distinte. Inoltre, vengono fornite $n$ voci, dove la $i$-esima voce è una sequenza di interi positivi di lunghezza $l_i$. Il tuo obiettivo è calcolare la rilevanza di ciascuna voce.

Input

La prima riga dell'input contiene un intero $m$ ($1 \le m \le 10$), che rappresenta la lunghezza della sequenza di parole chiave.

La riga successiva contiene $m$ interi $b_1, b_2, \dots, b_m$ ($1 \le b_i \le m$), che rappresentano la sequenza di parole chiave. È garantito che $b_1, b_2, \dots, b_m$ siano tutti distinti.

La riga successiva contiene un intero $n$ ($1 \le n \le 100$), che rappresenta il numero di voci.

Nelle successive $n$ righe: la $i$-esima riga contiene innanzitutto un intero $l_i$ ($1 \le l_i \le 10^6$), che rappresenta la lunghezza della $i$-esima voce, seguito da $l_i$ interi $a_{i,1}, a_{i,2}, \dots, a_{i,l_i}$ ($1 \le a_{i,j} \le 10^6$), che rappresentano il contenuto della $i$-esima voce.

È garantito che la lunghezza totale di tutte le voci non superi $10^6$.

Output

Stampa $n$ righe, dove la $i$-esima riga contiene un intero che rappresenta la rilevanza della $i$-esima voce.

Esempio

Input

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

Output

1
2
1

Note

Di seguito vengono usate sequenze di indici per rappresentare le sottosequenze.

• Per la prima voce, puoi scegliere $[1, 2, 3, 7]$ come sottosequenza; in tal caso $[a_1, a_2, a_3, a_7] = [4, 2, 1, 3]$, che è esattamente uguale alla sequenza di parole chiave.
• Per la seconda voce, puoi scegliere $[2, 3, 5, 9]$ e $[4, 6, 7, 8]$ come sottosequenze. Nota che $[2, 3, 7, 9]$ e $[4, 6, 7, 9]$ non possono essere scelte contemporaneamente come sottosequenze perché le loro posizioni si sovrappongono.