"Nick đỏ" kid2201 có một string ss chỉ gồm các kí tự latin thường.

Sau đó "nick cam" justys đến và đố rằng: "Hãy thêm đúng kk kí tự bất kì vào bên phải string ss, sao cho string ss có chuỗi con liên tục là chuỗi lặp song song dài nhất có thể."

Một string \(t\) có độ dài \(2n\) được gọi là chuỗi lặp song song, nếu với mỗi vị trí i(\(1 \leq i \leq n\)) thì \(s_{i}=s_{i+n}\). Ví dụ: aabaab, abcdabcd, aa, aaaa.

Vì là "nick đỏ" nên kid2201 biết thừa cách giải, nay justys đem đố lại các bạn học sinh để luyện tập lập trình.

Input

• Dòng đầu là xâu \(s\) (\(1 \leq s.size() \leq 200\))
• Dòng thứ 2 gồm số nguyên k (\(1 \leq k \leq 200\))

Output

• In ra độ dài lớn nhất có thể của chuỗi lặp song song là chuỗi con của string \(s\) sau khi thêm \(k\) kí tự.

Example

aaba
2

6

abbbb
2

6

abcde
5

10