Anna có một dãy gồm ~N~ thẻ, mỗi thẻ chỉ có chính xác một chữ cái từ ~A~ đến ~Z~. Các thẻ được đánh số ~1,2,...N~ từ trái sang phải.

Hôm nay, Anna được học về chuỗi đối xứng. Một chuỗi được gọi là chuỗi đối xứng khi viết chuỗi đó theo hướng từ trái sang phải hay từ phải sang trái đều giống nhau. Ví dụ, chuỗi ANNA, RACECAR, AAA, X là chuỗi đối xứng, trong khi đó AB, FROG, YOYO thì không là chuỗi đối xứng.

Bob muốn kiểm tra Anna xem Anna đã hiểu về chuỗi đối xứng tốt như thế nào bằng cách đưa ra ~Q~ câu hỏi. Với mỗi câu hỏi thứ ~i~, Anna cần trả lời câu hỏi: Liệu Anna có thể tạo ra một chuỗi đối xứng bằng cách sử dụng tất cả các thẻ có số thứ tự từ ~L_i~ đến ~R_i~ hay không? Có thể sắp xếp lại các thẻ nếu có thể. Sau mỗi câu hỏi, Anna cần đưa các thẻ về vị trí ban đầu.

Hãy giúp Anna bằng cách đếm xem có bao nhiêu câu hỏi của Bob mà Anna trả lời là "có thể".

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~T~ tương ứng với số test case.
• Với mỗi test case: Dòng đầu tiên chứa hai số nguyên ~N~ và ~Q~ lần lượt là số lượng khối và số câu hỏi. ~N~ dòng tiếp theo, mỗi dòng chứa một chuỗi các chữ cái in hoa (từ ~A~ đến ~Z~). ~Q~ dòng kế tiếp, mỗi câu hỏi thứ ~i~ sẽ gồm hai số nguyên ~L_i~ và ~R_i~ mô tả câu hỏi thứ i.

Dữ liệu ra

Với mỗi test case, dữ liệu ra gồm ~1~ dòng có dạng Case #x: y, với x là số thứ tự của test case (bắt đầu từ số ~1~), y là số câu hỏi mà Anna trả lời là "có thể".

Giới hạn

• ~1 \le T \le 100~
• ~1 \le L_i \le R_i \le N~

Subtask ~1~

• ~1 \le N \le 20~
• ~1 \le Q \le 20~

Subtask ~2~

• ~1 \le N \le 100000~
• ~1 \le Q \le 100000~

Sample Input

2
7 5
ABAACCA
3 6
4 4
2 5
6 7
3 7
3 5
XYZ
1 3
1 3
1 3
1 3
1 3

Sample Output

Case #1: 3
Case #2: 0

Giải thích

Ở ví dụ trường hợp #~1~, ~N=7~ và ~Q=5~:

• Ở câu hỏi thứ nhất, Anna phải sử dụng các thẻ AACC. Cô ấy có thể sắp xếp các thẻ lại thành ACCA (hoặc CAAC)
• Ở câu hỏi thứ hai, Anna phải sử dụng thẻ A. Đây đã là chuỗi đối xứng nên không cần phải sắp xếp lại.
• Ở câu hỏi thứ ba, Anna phải sử dụng các thẻ BAAC. Không cách nào để sắp xếp các thẻ thành chuỗi đối xứng.
• Ở câu hỏi thứ tư, Anna phải sử dụng các thẻ CA. Không cách nào để sắp xếp các thẻ thành chuỗi đối xứng.
• Ở câu hỏi thứ năm, Anna phải sử dụng các thẻ AACCA. Cô ấy có thể sắp xếp các thẻ lại thành ACACA (hoặc CAAAC)

Tổng cộng, có ~3~ câu hỏi của Bob mà Anna trả lời là "có thể".

Ở ví dụ trường hợp #~2~, ~N=3~ và ~Q=5~, Anna phải sử dụng các thẻ XYZ để tạo chuỗi đối xứng. Không có cách nào để sắp xếp trong khi đó các câu hỏi còn lại của Bob đều giống với câu đầu tiên, nên đáp án là ~0~.