DNA được cấu tạo theo nguyên tắc đa phân mà đơn phân là nucleotide gồm ~4~ loại A, T, G, C. Một đoạn phân tử DNA có các nucleotide trên một mạch sắp xếp theo một trình tự nhất định.

An được giao nhiệm vụ kiểm tra tình trạng của ~N~ đoạn DNA để báo cáo cho một bài nghiên cứu về di truyền. Trong đó, đoạn DNA được xem là bất thường nếu các nucleotide có ít nhất một trong ba trường hợp sau:

• Độ đa dạng nucleotide thấp: có ít hơn ~3~ loại nucleotide khác nhau.

• Nucleotide đơn lẻ: có ít nhất một loại nucleotide chỉ xuất hiện đúng ~1~ lần trong toàn đoạn.

• Khoảng cách giữa các nucleotide cùng loại lớn hơn ngưỡng ~K~; khoảng cách giữa hai vị trí ~i~ và ~j~ ~(1 \le i < j \le N)~ được tính bằng cách lấy ~j~ trừ ~i~.

An kiểm tra lần lượt từng đoạn DNA theo thứ tự đã cho, nếu bất thường đánh dấu là ~1~, ngược lại đánh dấu là ~0~. Sau khi hoàn thành nhiệm vụ, An có được một chuỗi nhị phân có độ dài ~N~. Tiếp theo, An chuyển chuỗi nhị phân này thành số hệ thập phân để thuận lợi trong việc nhập kết quả báo cáo.

Yêu cầu: Dựa trên ~N~ đoạn DNA và ngưỡng ~K~ cho trước, viết chương trình cho biết số thập phân mà An đã tính được để báo cáo.

Input

Dòng 1: hai số nguyên dương ~N~ và ~K~ ~(1 \le N \le 10, 1 \le K \le 10^5)~.

~N~ dòng tiếp theo, mỗi dòng gồm một chuỗi ~S_i~ có độ dài tối đa là ~10^5~, các kí tự chỉ bao gồm: A, T, G, C.

Output

Ghi ra một số nguyên duy nhất là kết quả báo cáo.

Scoring

Sample Input 1

3 4
AATTGGCC
AATTGCC
TAAGGT

Sample Output 1

3

Sample Input 2

4 3
ATGC
AATTGG
CGGC
CGCGTATA

Sample Output 2

10

Notes

Ví dụ 1:

• Đoạn DNA 1: bình thường (đánh dấu ~0~).

• Đoạn DNA 2: bất thường do nucleotide G xuất hiện đúng một lần (đánh dấu ~1~).

• Đoạn DNA 3: bất thường do khoảng cách giữa hai nucleotide T liên tiếp là ~6 - 1 = 5 > 4~ (đánh dấu ~1~).

An có được chuỗi nhị phân là ~011~, chuyển sang hệ thập phân là ~3~.

Ví dụ 2:

• Kết quả kiểm tra lần lượt là: bất thường, bình thường, bất thường, bình thường.

An có được chuỗi nhị phân là ~1010~, chuyển sang hệ thập phân là ~10~.