Phân biệt

Cho xâu ký tự \(S\) và số nguyên dương \(k\). Gọi \(T\) là xâu thu được bằng cách ghép liên tiếp \(k\) bản sao của \(S\).

Ta được phép thực hiện thao tác sau nhiều lần: chọn một ký tự bất kỳ trong \(T\) và thay nó bằng một chữ cái in thường khác.

Yêu cầu: Tìm số thao tác ít nhất cần thực hiện để trong \(T\) không còn hai ký tự kề nhau nào giống nhau.

Input

• Dòng đầu tiên chứa xâu \(S\) gồm \(n\) chữ cái in thường (\(1 \le n \le 100\)).

• Dòng thứ hai chứa số nguyên \(k\) (\(1 \le k \le 10^9\)).

Output

Một số nguyên duy nhất là số thao tác ít nhất cần thực hiện.

Notes

Với $S = $ issii và \(k = 2\): xâu \(T\) là issiiissii, ta có thể thay \(4\) ký tự để được ispiqisyhi, nên đáp án là \(4\).