Problem description

Transport wojsk podczas wojny nuklearnej to trudne zadanie. Częste naloty i skażenie uniemożliwia przejście z jednego okopu do drugiego. Potrzebny jest plan działania i ulepszenie systemu obronnego.

Każdy z okopów jest reprezentowany przez unikalną liczbę opisującą jego znaczenie strategiczne. Z okopu o wartości a da się przejść do okopu o wartości b, jeżeli liczby a oraz b nie są względnie pierwsze, tj. istnieje dzielnik d > 1, który dzieli zarówno a, jak i b.

Ta nietypowa struktura wprowadziła dowództwo w zakłopotanie. Czasami nie da się przejść pomiędzy okopami bez narażenia odziału na stratę. Podstanowiono podjąc jedyną sensowną decyzję: trzeba budować nowe okopy obok już istniejących. To znaczy, dla wybranego okopu o wartości a_i jest budowany nowy o wartości (a_i+1) ⋅ a_i, oczywiście jeżeli taki jeszcze nie istnieje.

Pomóż im i odpowiedz na Q niezależnych zapytań o minimalną liczbę nowych okopów, które należy wybudować, aby możliwe było bezpiecznie poruszać się pomiędzy okopami o wartościach a_sj oraz a_tj.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby N oraz Q oznaczające liczbę okopów oraz liczbę zapytań.

Następnie podane są N różnych liczb całkowitych a₁, a₂, …, a_N, będące wartościami już istniejących okopów.

Kolejne Q wierszy zawiera pary liczb całkowitych t_j i s_j, reprezentujące indeksy okopów w zapytaniach.

Wyjście

Wypisz dokładnie Q wierszy, gdzie j-ty z nich powinien zawierać jedną liczbę — minimalną liczbę nowych okopów, które trzeba zbudować, aby oddział mógł bezpiecznie poruszać się pomiędzy okopami a_sj oraz a_tj.

Ograniczenia

2 ≤ N ≤ 150 000, 1 ≤ Q ≤ 300 000, 2 ≤ a_i ≤ 10⁶, a_i ≠ a_j jeżeli i ≠ j, 1 ≤ s_j, t_j ≤ N, s_j ≠ t_j.

Podzadania

Przykład

3 3
2 10 3
1 2
1 3
2 3

0
1
1

5 12
3 8 7 6 25
1 2
1 3
1 4
1 5
2 1
2 3
2 4
2 5
3 1
3 2
3 4
3 5

0
1
0
1
0
1
0
1
1
1
1
2