Zadanie

Cyrilove metódy

Počet bodov: 20

Cyril nevie poriadne vyslovovať. Prišiel však s metódou, ako si to poriadne precvičiť.

Zaobstaral si certifikovaný logopedický reťazec pozostávajúci z písmen anglickej abecedy.

Plánuje ho celý vysloviť.

Zaujíma ho však, či si všetko dobre precvičí - vysloví naozaj každú dvojicu písmen, ktorá ho zaujíma, dosť často?

Vstup a výstup

V prvom riadku vstupu je číslo \(n\) - dĺžka reťazca.

V druhom riadku vstupu je logopedický reťazec \(s\).

V treťom riadku vstupu je číslo \(q\) - koľko dvojíc písmen Cyrila zaujíma.

V nasledovných \(q\) riadkoch sú tieto reťazce dĺžky dva.

Pre každú dvojicu písmen čo Cyrila zaujíma, zrátajte koľko krát sa vyskytuje v jeho logopedickom reťazci, a vypíšte to na samostatný riadok.

V prvej sade \(1 \leq n, q \leq 1000\). V druhej sade \(1 \leq n,q \leq 200\,000\).

Príklady

Input:

9
abbaaabxy
3
ab
aa
bx

Output:

2
2
1