Cho xâu kí tự ~S~, gọi ~T~ là xâu ghép của ~k~ xâu ~S~. Chúng ta được phép thực hiện thao tác sau: Chọn ~1~ kí tự bất kì trong xâu ~T~ và thay nó bằng một kí tự khác bất kì sao cho sau khi thực hiện thao tác đó thì hai kí tự liên tiếp của xâu ~T~ là phân biệt. Các kí tự trong xâu ~S~ là chữ cái in thường và khi thay thế cũng phải thay thế bằng kí tự in thường.

Yêu cầu: Hãy đếm số kí tự ít nhất phải thay đổi để hai kí tự liên tiếp của xâu ~T~ là phân biệt.

Input

• Dòng 1: Là xâu ~S~ có độ dài không quá ~100~ kí tự.

• Dòng 2: Là số ~k~ ~(1 \le k \le 10^{9})~.

Output

Một số nguyên duy nhất là số kí tự ít nhất phải thay đổi để hai kí tự liên tiếp của xâu ~T~ là phân biệt.

Scoring

Sample Input 1

abbc
2

Sample Output 1

2

Sample Input 2

abc
3

Sample Output 2

0

Notes

• Test 1: Xâu ~T~ là "abbcabbc". Ta có thể thay thế thành: "apbcapbc".

• Test 2: Xâu ~T~ là "abcabcabc" thoả mãn hai kí tự liên tiếp của xâu ~T~ là phân biệt (chúng ta không cần thực hiện thao tác nào).