Cho một xâu ~S~ chỉ gồm các kí tự chữ cái thường ('a' đến 'z'). Một xâu ~P~ được gọi là nén gần đúng với lỗi ~e~ nếu khoảng cách Hamming của xâu ~S~ với xâu ~T~ không vượt quá ~e~ kí tự, trong đó ~T~ là tiền tố của xâu ~P + P + \dots + P~ có độ dài bằng độ dài xâu ~S~. Với một xâu ~W~, cần tìm cách thay thế không quá ~k~ kí tự để nhận được ~W'~ là xâu nén gần đúng của xâu ~S~ với lỗi nhỏ nhất.

Yêu cầu: Cho xâu ~S~ và số nguyên ~k~, với mỗi xâu trong ~m~ xâu ~W_1, W_2, \dots, W_m~, hãy cách thay đổi không quá ~k~ kí tự để nhận được xâu mới là xâu nén gần đúng của xâu ~S~ với lỗi là nhỏ nhất.

Input

• Dòng đầu chứa số nguyên ~m~ và ~k~ (~k \le 100; m \le 1000~).
• Dòng tiếp theo chứa xâu ~S~ (~|S| \le 10000~).
• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa xâu ~W_i~ (~|W_i| \le 100~).

Output

• Ghi ra ~m~ dòng, mỗi dòng chứa một số nguyên là lỗi nhỏ nhất tương ứng với từng xâu trong ~m~ xâu.

Sample Input 1

2 1
abab
bb
c

Sample Output 1

0
2