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?

Input

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 ≤ K ≤ 10⁶ (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⁵.

Output

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

Example Input

8
ada 3
abc 2
r 7
rr 5
gorego 3
abbababbbbababababba 2
abcabcabca 3
lopadotemachoselachogaleokranioleipsanodrimhypotrimmatosilphioparaomelitokatakechymenokichlepikossyphophattoperisteralektryonoptekephalliokigklopeleiolagoiosiraiobaphetraganopterygon 1

Example Output

7
6
7
6
14
36
16
182