== include(page="template/taskheader" task_id="kpal") ==

Se considera K numere naturale: b_1, b_2,..., b_K. Spunem ca un numar X in baza 10 este K - palindrom daca exista un indice i, 1≤i≤K, cu proprietatea ca numarul X scris in baza b_i este palindrom.

Se considera K numere naturale: b[~1~], b[~2~],..., b[~K~]. Spunem ca un numar X in baza 10 este K - palindrom daca exista un indice i, 1≤i≤K, cu proprietatea ca numarul X scris in baza b[~i~] este palindrom.

Un numar este palindrom daca se citeste la fel de la stanga la dreapta si de la dreapta la stanga.
Se cere sa se raspunda la Q intrebari de tipul:
L  U: cate numere cuprinse in intervalul [L,U] sunt K - palindroame?
h2. Date de intrare

Pe prima linie a fisierului de intrare $kpal.in$ se afla K. Pe a doua linie sa afla K numere naturale b_1, b_2,..., b_K separate prin cate un spatiu. Pe a treia linie sa afla numarul Q. Pe urmatoarele Q linii se afla cate doua numere naturale L si U separate printr-un spatiu care reprezinta cele Q intrebari.

Pe prima linie a fisierului de intrare $kpal.in$ se afla K. Pe a doua linie sa afla K numere naturale b[~1~], b[~2~],..., b[~K~] separate prin cate un spatiu. Pe a treia linie sa afla numarul Q. Pe urmatoarele Q linii se afla cate doua numere naturale L si U separate printr-un spatiu care reprezinta cele Q intrebari.

h2. Date de ieşire

In fisierul de iesire $kpal.out$ se vor afla Q linii. Pe linia i^ se va afla raspunsul la intrebarea i.

In fisierul de iesire $kpal.out$ se vor afla Q linii. Pe linia i se va afla raspunsul la intrebarea i.

h2. Restricţii