SP34020 ADAPET - Ada and Pet

Ada the Ladybug just got herself a new pet. She was thinking about a name for it. She thought-up a beautiful name for it already but now she doesn't think this name is "enough". She wants to find a new name, which will contain the original name at least **K** times as substring (to emphasize its importance). As ada doesn't want the pet's name to be too long, she wants to find the shortest one - can you find the length of it?

The first line of input will contain **T**, the number of test-cases. Each of the next **T** lines will contain a non-empty string **s**, consisting of lowercase-english letters and a number **1 (the number of times the given name shall be in the new name).** The sum of lengths of strings over all test-cases will not exceed **5\*10 $ ^{5} $** .

For each test-case print the minimum length of new name.