Minimizing Strict Cyclic Period Length

Given a string s consisting only of lowercase English letters, you are allowed to perform at most k operations. In each operation, you may choose any character from s and change it to any lowercase English letter.

You can perform no more than k operations (in any order, and possibly none) in order to minimize the length of s's strict cyclic period. A string t is called a strictly cyclic period of s if and only if s can be constructed by concatenating one or more copies of t. For instance, mai is a strict cyclic period of maimai, and dx is a strict cyclic period of dx, but ov is not a strict cyclic period of ovo.

Output the minimum possible length of the strict cyclic period of s after performing at most k operations.

inputFormat

The input consists of two lines:

• The first line contains the string s (only lowercase English letters).
• The second line contains an integer k, representing the maximum number of allowed operations.

outputFormat

Output a single integer — the minimum possible length of s's strict cyclic period after performing at most k operations.

sample

aba
1

1