Trong lớp học toán ngày hôm nay của Cirno, cô ra một bài toán cho các học sinh của mình:

Cho một số nguyên dương, hãy đếm số cách xóa bỏ một chữ số (số còn lại có thể có số 0 ở đầu) để số còn lại chia hết cho 3, nhưng không chia hết cho 9 (vì cô không thích số 9).

Input:

• Một số nguyên dương ~n \le 10^{100000}~.

Output

• Số cách xóa thỏa mãn.

Sample Test

Input:

396

Output:

2

Giới hạn

• 60% số điểm: ~n \le 10^{1000}~
• 40% số điểm: Không có giới hạn gì thêm.

Hôm nay lại có ~n~ gian hàng bán đồ ăn tại lễ hội ở đền Hakurei. Yuyuko tham ăn có ~q~ lựa chọn dạng ~l_i, r_i~, đi ăn tất cả cửa hàng ở vị trí ~l_i~ đến vị trí ~r_i~.

Nhưng hôm nay do quá đói, cô đã đi ăn ~m~ lần, sử dụng tất cả các lựa chọn từ ~x_i~ đến ~y_i~. Với mỗi gian hàng, hãy in ra số lần cô ghé thăm.

Input:

• Dòng đầu gồm 3 số tự nhiên ~n, q, m~.
• ~q~ dòng tiếp theo mỗi dòng gồm 2 số ~1 \le l_i, r_i \le n~ là lựa chọn thứ ~i~.
• ~m~ dòng tiếp theo mỗi dòng gồm 2 số ~1 \le x_i, y_i \le q~ là lượt đi ăn thứ ~j~.

Output:

• ~n~ số nguyên không âm là số lần cô ghé thăm các gian hàng.

Sample Test:

• Input:

3 3 3
1 2
2 3
1 3
2 3
1 2
1 3

• Output

4 7 5

Giới hạn:

• 40% số điểm: ~n, q, m \le 100~.
• 30% số điểm: ~n, q, m \le 5000~.
• 30% số điểm: ~n, q, m \le 10^5~

Tewi đã ốm liệt giường nên Yagokoro Eirin phải chữa bệnh cho cô. Đoạn ADN của Tewi có độ dài ~n~ gồm cách kí tự ~a, b, c~ (vì sao thì chưa rõ). Eirin có thể sửa đổi một vị trí bất kì trên ADN với chi phí là 1.

Cô đang nghi ngờ ~q~ đoạn con ~[l_i, r_i]~ có thể là nguyên nhân gây bệnh. Với mỗi đoạn ADN con này, Eirin muốn sửa lại đoạn này sao cho không tồn tại đoạn con nào có độ dài lớn hơn 1 là xâu đối xứng. Ví dụ ~aab~ là không thỏa mãn vì có ~aa~ là xâu đối xứng. Hãy giúp cô tính trước chi phí để chữa bệnh nhé!

Input:

• Dòng đầu tiên gồm 2 số ~n, q~.
• Dòng tiếp theo là một xâu gồm ~n~ kí tự chỉ gồm ~a, b, c~.
• ~q~ dòng tiếp theo mỗi dòng gồm 2 số ~l_i, r_i~.

Output:

• ~q~ dòng là chi phí chữa bệnh.

Sample Test

Input:

5 4
baacb
1 3
1 5
4 5
2 3

Output:

1
2
0
1

Giới hạn:

• Trong mọi test ~n, q \le 10^5~
• 10% số điểm: ~n, q \le 5~.
• 30% số điểm: ~n, q \le 2000~.
• 30% số điểm: ADN chỉ gồm 2 kí tự ~a, b~.
• 30% số điểm: Không có giới hạn gì thêm.

Marisa muốn nấu ăn bằng một số loại thảo mộc cô mới hái được. Mỗi loại có một độ độc nhất định, tuy vậy nếu kết hợp các loại thảo mộc mà tích độ độc của chúng bằng bội chung nhỏ nhất của chúng thì độc tố sẽ biến mất.

Có ~q~ ngày, ngày thứ ~q~ Marisa muốn chọn các loại thảo mộc từ vị trí ~l~ đến vị trí ~r~ để nấu ăn, mỗi món ăn sẽ được nấu từ các thảo mộc liên tiếp và phải không có độc. Hãy giúp cô tính số lượng món ăn ít nhất có thể nấu được vì nhiều quá cô sẽ không ăn hết.

Input

• Dòng đầu tiên gồm 2 số nguyên dương ~n, q~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~a_i~ là độ độc của món ăn thứ ~i~.
• ~q~ dòng tiếp theo gồm 2 số ~l_i, r_i~ .

Output:

• Gồm ~q~ số nguyên dương là đáp án của ~q~ ngày.

Sample Test:

Input

5 2
2 3 10 7 5
2 4
3 5

Output:

1
2

Giải thích:

• Ở test 1, 3 số 3 10 7 có tích bằng với bội chung nhỏ nhất là 210 nên có thể chia thành 1 đoạn.
• Ở test 2, có thể chia thành đoạn 10 và 7 5, không thể có kết quả nhỏ hơn.

Giới hạn:

• Trong mọi test ~a_i \le 10^5~.
• 25% số điểm: ~n, q \le 100~.
• 25% số điểm: ~n, q \le 1000~.
• 25% số điểm: ~a_i~ là các số nguyên tố.
• 25% số điểm: ~n, q \le 10^5~.