ADAPET - Ada and Pet

no tags 

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 ≤ 106 (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*105.

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

hide comments
monukumar: 2018-01-18 17:49:32

Don't forget long :D

hanstan: 2018-01-10 17:38:04

Nailed it 0.00s xD

trishala_naman: 2018-01-06 21:51:03

Finally AC in 0.11s. Thanks @morass for that example :)

manya_cod4: 2018-01-06 09:12:35

From TLE -> WA -> AC in 1.05 - > AC in 0.13. Thanks @shubham_001 and @morass.

manya_cod4: 2018-01-05 15:55:06

@morass. Hi. Now i get your hint :P. but could never have guessed. I didnt know that concept. And Thanks for setting so many awesome questions. I always learn something new solving questions set by you. :).

manya_cod4: 2018-01-05 15:52:33

@shubham. Hi. Thanks for replying on my help thread. Seriously. learnt something new today.

shubham_001: 2018-01-04 12:25:01

@manya_cod4 Nice if you go with your first comment :)

manya_cod4: 2018-01-03 23:23:57

@morass : Thanks a lot for such a fast reply. Will now try to work out your hints. and Thanks again!!

morass: 2018-01-03 23:18:56

@manya_cod4:

Hint I) Why don't you try big strings too?

Hint II) Hamming distance between your code and AC code could be "2 characters"

Good Luck ;-)

manya_cod4: 2018-01-03 23:15:39

@morass.Good day to you. Thanks for the reply. I implemented my logic in c++. Now I am getting WA. Thanks again for the help.


Added by:Morass
Date:2017-12-31
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All