Problem description

Pan Janusz (szef szefów w Januszex S.A.) polecił przygotować wiele billboardów w celu promocji jego firmy. Na każdym billboardzie miał pojawić się napis januszex. Niestety pracownik przygotowujący billboardy przygotował tylko jeden długi ciąg literek. Pan Janusz się wściekł, ale poważny biznesmen powinien uratować każdą, nawet tragiczną sytuację. Oto co Pan Janusz wymyślił: wybierze z napisu pewien spójny fragment od pewnej do pewnej pozycji, następnie potnie ten fragment na kilka kawałków (osobnych billboardów). W każdym kawałku słowo januszex musi się pojawić jako podciąg (niekoniecznie spójny), a niepotrzebne literki czymś się zakryje i będzie dobrze.

W zasadzie, nie ma absolutnie żadnej potrzeby, żeby najpierw z napisu wybierać spójny kawałek i tylko na nim się skupiać, bo to tylko utrudnia zadanie, ale Pan Janusz nie chce się przyznać do tego, że jego plan można uprościć, dlatego należy wykonać jego zadanie szybko, nawet dla wielu różnych pozycji początkowych i końcowych.

Napisz program, który: wczyta wydrukowany napis oraz zapytania Pana Janusza o przeprowadzenie procedury cięcia spójnego kawałka na billboardy, wyznaczy dla każdego z nich maksymalną liczbę billboardów, które można utworzyć i wypisze wyniki na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N oraz Q, oddzielone pojedynczym odstępem i określające kolejno: długość napisu oraz liczbę zapytań. W drugim wierszu znajduje się ciąg małych liter alfabetu angielskiego – wydrukowany napis. W kolejnych Q wierszach znajduje się opis kolejnych zapytań. Opis każdego zapytania składa się z dwóch liczb naturalnych A_i oraz B_i oddzielonych pojedynczym odstępem i określających pozycje: początkową i końcową wybranego kawałka napisu, dla którego należy przeprowadzić procedurę Pana Janusza.

Wyjście

Twój program powinien wypisać na wyjście dokładnie Q wierszy. W i-tym wierszu powinna się znaleźć odpowiedź dla i-tego zestawu danych. Odpowiedź dla każdego zestawu danych to jedna liczba całkowita – maksymalna liczba billboardów, które można wyciąć z fragmentu wybranego przez Pana Janusza tak, aby każdy z nich zawierał w sobie jako podciąg słowo januszex.

Ograniczenia

1 ≤ N ≤ 200 000, 1 ≤ Q ≤ 200 000, 1 ≤ A_i ≤ B_i ≤ N.

Przykład

22 5
qjanujaszexjanuqszexjx
1 21
5 16
12 20
2 11
13 21

2
0
1
1
0