Nhằm đảm bảo an toàn cho các tàu thuyền đánh bắt thủy hải sản và du lịch di chuyển qua khu vực đá ngầm xung quanh ngọn hải đăng trên một vùng biển của tỉnh Alpha, đội quản lý được giao nhiệm vụ dựng các tháp phao cảnh báo trên biển.

Trong kho vật tư có ~n~ khối phao tròn có kích thước từ ~1~ đến ~n~. Mỗi khối phao mang một màu sắc đỏ (ký hiệu R) hoặc xanh (ký hiệu B). Các khối phao được dùng để xếp chồng lên nhau tạo thành các tháp phao thả trên biển. Để đứng vững trước sóng gió và đạt chuẩn an toàn, tháp phao phải được xây dựng theo hai quy tắc như sau:

• Hai khối phao nằm chồng trực tiếp lên nhau không được phép cùng màu.

• Tất cả các khối phao nằm phía trên một khối phao bất kỳ trong cùng một tháp phải có kích thước nhỏ hơn khối phao ở phía dưới nó (đáy tháp là phao to nhất, đỉnh tháp là phao nhỏ nhất).

Đội trưởng đưa ra ~q~ nhiệm vụ, mỗi nhiệm vụ yêu cầu cần sử dụng toàn bộ các khối phao có kích thước nằm trong đoạn từ ~l_i~ đến ~r_i~.

Yêu cầu: Với mỗi nhiệm vụ, hãy tính số lượng tháp phao ít nhất cần phải xây dựng sao cho dùng đúng và đủ các khối phao trong đoạn ~[l_i, r_i]~ và tất cả các tháp phao đều tuân thủ hai quy tắc xây dựng trên.

Input

• Dòng đầu tiên chứa ~2~ số nguyên dương ~n~ và ~q~ ~(1 \le n, q \le 10^5)~ tương ứng là số lượng khối phao và số lượng nhiệm vụ;

• Dòng thứ hai là một chuỗi ~s~ có độ dài ~n~ chỉ gồm các ký tự R và B. Ký tự thứ ~i~ đại diện cho màu của khối phao có kích thước ~i~;

• ~q~ dòng tiếp theo, mỗi dòng chứa ~2~ số nguyên ~l_i, r_i~ ~(1 \le l_i \le r_i \le n)~ mô tả phạm vi kích thước phao của nhiệm vụ thứ ~i~.

Output

Gồm ~q~ dòng, mỗi dòng chứa một số nguyên là số lượng tháp phao tối thiểu cần xây dựng cho mỗi nhiệm vụ.

Scoring

Sample Input 1

7 4
BBRBBRR
1 7
1 5
3 7
4 5

Sample Output 1

3
3
2
2

Notes

Nhiệm vụ ~1~ ở ví dụ trên có ~l = 1, r = 7~, dùng tất cả các khối ~[1, 2, 3, 4, 5, 6, 7]~ tương ứng các màu B, B, R, B, B, R, R. Ta có một trong những cách có thể xây dựng ít nhất là ~3~ tháp phao. Cụ thể:

• Tháp ~1~: khối ~1~ (B), khối ~3~ (R), khối ~4~ (B), khối ~6~ (R).

• Tháp ~2~: khối ~2~ (B), khối ~7~ (R).

• Tháp ~3~: khối ~5~ (B).