Bitaro làm việc tại một cửa hàng bánh pancake. Món được yêu thích nhất là tháp gồm \(N\) chiếc bánh pancake xếp chồng lên nhau. Cửa hàng có ba hương vị bánh, được ký hiệu là A, B, C.

Một tháp bánh được gọi là tháp bánh tốt nếu cách xếp bánh thỏa mãn tất cả các điều kiện sau:

• Với mọi cặp bánh vị A và bánh vị B, bánh vị A nằm phía trên bánh vị B.
• Với mọi cặp bánh vị A và bánh vị C, bánh vị A nằm phía trên bánh vị C.
• Với mọi cặp bánh vị B và bánh vị C, bánh vị B nằm phía trên bánh vị C.

Ví dụ, các tháp có hương vị từ trên xuống lần lượt là AABBBC, ACC, BBBB đều là tháp bánh tốt; các tháp AABABCC, CA thì không.

Bitaro phụ trách bày bánh và có thể thực hiện thao tác sau:

Thao tác \(k\) (\(2 \le k \le N\)): luồn xẻng lật bánh xuống dưới chiếc bánh thứ \(k\) tính từ trên xuống rồi lật ngược phần bánh phía trên xẻng. Nói cách khác, đảo ngược thứ tự của \(k\) chiếc bánh trên cùng.

Chẳng hạn, với tháp có hương vị từ trên xuống là ABCB, nếu thực hiện riêng từng thao tác \(2\), \(3\), \(4\) trên tháp ban đầu thì lần lượt thu được BACB, CBAB, BCBA.

Hiện có \(Q\) đĩa tháp bánh. Đĩa thứ \(i\) (\(1 \le i \le Q\)) có các hương vị từ trên xuống là \(S_{i,1}S_{i,2}\ldots S_{i,N}\). Bitaro muốn biến từng tháp thành tháp bánh tốt với số thao tác ít nhất có thể.

Cho thông tin về \(Q\) tháp bánh, hãy viết chương trình tìm số thao tác ít nhất cần thực hiện cho mỗi tháp.

Dữ liệu vào

Dòng thứ nhất chứa hai số nguyên \(N, Q\).

Trong \(Q\) dòng tiếp theo, dòng thứ \(i\) chứa xâu \(S_i\) có độ dài \(N\), trong đó ký tự thứ \(j\) là \(S_{i,j}\), mô tả hương vị từ trên xuống của tháp bánh thứ \(i\).

Dữ liệu ra

In ra \(Q\) dòng. Dòng thứ \(i\) (\(1 \le i \le Q\)) chứa số thao tác ít nhất cần thực hiện để biến tháp bánh thứ \(i\) thành tháp bánh tốt.

Ràng buộc

• \(2 \le N \le 13\).
• \(1 \le Q \le 100\,000\).
• \(S_{i,j}\) là A, B hoặc C với mọi \(1 \le i \le Q\), \(1 \le j \le N\).

Phân nhóm

Mọi phân nhóm đều thỏa mãn các ràng buộc chung ở trên.

1. (4 điểm) \(N \le 5\), \(Q=1\).
2. (10 điểm) \(N \le 5\).
3. (60 điểm) \(Q=1\).
4. (26 điểm) Không có ràng buộc bổ sung.

Ví dụ

5 3
ABCBA
CCBAB
AAAAA

3
2
0

2 5
AC
AC
AC
AC
AC

0
0
0
0
0

13 1
ABCCABCBACBAA

9

13 4
CCAAACBAAAABB
BBBCCBCCCBCBC
CCCAAAABBBBBB
AABCBCACBACBA

4
6
2
10

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.