Cho một chuỗi nhị phân ~t~=~t_1~~t_2~ ... ~t_m~ chỉ gồm các ký tự 0 và 1.

Các cặp ký tự kề nhau được xét gồm: ~t_1t_2,\ t_2t_3,\ldots,t_{m-1}t_m~ và thêm cặp ~t_mt_1~ tức là ký tự cuối được nối vòng với ký tự đầu. Do đó có đúng m cặp được xét.

Nếu chuỗi chỉ có một ký tự, cặp duy nhất là t1t1.

Chuỗi t được gọi là cân bằng tuần hoàn nếu số lượng của bốn loại cặp

• 00
• 01
• 10
• 11

đều bằng nhau.

Chi phí của một chuỗi

Chi phí của một chuỗi nhị phân là số ký tự ít nhất cần chèn thêm để biến nó thành một chuỗi cân bằng tuần hoàn.

Có thể chèn 0 hoặc 1 vào bất kỳ vị trí nào, kể cả trước ký tự đầu hoặc sau ký tự cuối. Không được xóa hoặc thay đổi các ký tự ban đầu.

Cho chuỗi nhị phân s và q truy vấn.

Mỗi truy vấn cho hai chỉ số l và r.

Hãy tìm chi phí của chuỗi con ~s_ls_{l+1}\ldots s_r.~

Input

Dòng đầu chứa hai số nguyên:

~1 \le n,q \le 3\cdot10^5~

trong đó:

• n là độ dài chuỗi.
• q là số truy vấn.

Dòng tiếp theo chứa chuỗi nhị phân s có độ dài n.

q dòng tiếp theo, mỗi dòng chứa: l r

Input

11 7
00111100000
1 8
1 1
1 2
1 4
3 6
2 7
7 11

Output

4
3
2
0
4
2
7 

Giải thích:

Truy vấn 1 1: chuỗi con là 0. Chèn thêm 011 để được 0011. Khi nối vòng, các cặp 00, 01, 11, 10 đều xuất hiện đúng 1 lần. → Cần 3 lần chèn.

Truy vấn 1 2: chuỗi con là 00. Chèn thêm 11 để được 0011, đây là chuỗi cân bằng tuần hoàn. → Cần 2 lần chèn.

Truy vấn 1 4: chuỗi con là 0011. Các cặp khi nối vòng là: 00, 01, 11, 10, mỗi loại xuất hiện đúng 1 lần. → Chuỗi đã cân bằng, đáp án là 0.

Truy vấn 2 7: chuỗi con là 011110. Có thể chèn thêm 2 ký tự 0 để tạo một chuỗi cân bằng như 00110110. → Đáp án là 2.