== include(page="template/taskheader" task_id="deletegcd") ==
Un şir se numeşte $şmecher$ dacă cel mai mare divizor comun al tuturor elementelor lui este diferit de $1$. Un şir se numeşte $aproape-şmecher$ dacă prin ştergerea unui singur element al său acesta devine $şmecher$.

Se dă un şir de numere naturale $A$ de lungime $n$ şi $q$ întrebări. La o întrebare, se dau 2 indici $l$ şi $r$ şi se cere să determinaţi daca subsecvenţa de la $l$ la $r$ a şirului $A$ este un şir $aproape-şmecher$. În particular, un şir care este $şmecher$ este considerat şi $aproape-şmecher$.

Se dă un şir de numere naturale $A$ de lungime $n$ şi $q$ întrebări. La o întrebare, se dau 2 indici $l$ şi $r$ şi se cere să determinaţi dacă subsecvenţa de la $l$ la $r$ a şirului $A$ este un şir $aproape-şmecher$. În particular, un şir care este $şmecher$ este considerat şi $aproape-şmecher$.

h2. Date de intrare
Fişierul $deletegcd.in$ conţine $q+2$ linii.
Pe prima linie apar $n$ şi $q$.

Pe următoarea linie apar $n$ numere,reprezentând elementele şirului $A$ .
Pe urmatoarele $q$ linii apar câte 2 numere,reprezentând parametrii $l$ şi $r$ pentru cele $q$ query-uri.

Pe următoarea linie apar $n$ numere, reprezentând elementele şirului $A$ .
Pe urmatoarele $q$ linii apar câte 2 numere, reprezentând parametrii $l$ şi $r$ pentru cele $q$ query-uri.

h2. Date de ieşire

* $1 ≤ Q ≤ 10^6^$
* $1 ≤ l < r ≤ N$
* $1 ≤ A[i] ≤ 10^6^$

* Toate secventele din întrebări au lungime cel puţin 3.
* Pentru $15$ puncte, $1 ≤ N, Q, A[i] ≤ 10^2^$
* Pentru alte $20$ de puncte $1 ≤ N, Q, A[i] ≤ 10^3^$
* Pentru alte $40$ de puncte $1 ≤ N, Q, A[i] ≤ 2*10^5^$
* Pentru restul de $25$ de puncte, se aplică restricţiile iniţiale

* Toate secvenţele din întrebări au lungime cel puţin 3.
* *Atenţie!Testele sunt grupate*
* $Pentru 15 puncte, 1 ≤ N, Q, A[i] ≤ 10^2^ (grupa testelor 1-3)$
* $Pentru alte 20 de puncte 1 ≤ N, Q, A[i] ≤ 10^3^ (grupa testelor 4-7)$
* $Pentru alte 40 de puncte 1 ≤ N, Q, A[i] ≤ 2*10^5^ (grupa testelor 8-15)$
* $Pentru restul de $25$ de puncte, se aplică restricţiile iniţiale (grupa testelor 16-20)$

* *ATENŢIE! Se recomandă parsarea fişierului $deletegcd.in$. Puteţi folosi codul oferit de noi pe siteul 'in':http://www.infoarena.ro/parsare-fisier-intrare (atât pentru utilizatorii de $C++$ şi sintaxă similară cu $fstream$, cât şi pentru iubitorii de $C$ pur)*
* *De asemenea, se recomandă să afişaţi ieşirea ca un şir de caractere (nu câte un caracter).*