Dadas wants to finish a text of length , consisting of lowercase English letters. Initially, all positions are empty. Writing one letter by hand costs units of effort.
To reduce the effort, Dadas may create one stamp bearing a string of his choice. If that string has length , creating the stamp costs units of effort. Creating a stamp is optional, and at most one kind of stamp may be created.
A stamp can be used as follows.
For example, suppose the text is abcabca and the stamp bears abca. Stamp positions through , then positions through . This completes the entire text. Position receives the letter a twice, which is allowed.
Positions not covered by the stamp must be written by hand. Find the minimum effort needed to complete .
The input has the following format:
For each test case, print the minimum effort needed to complete on a separate line.
In the first test case, creating an abca stamp costs . Using it starting at positions and completes abcabca. Using the stamp requires no additional effort.
In the second test case, it is best to create no stamp and write all five letters by hand, costing .
is the number of test cases. Each case has the following format:
is the text length, is the effort to write one letter by hand, and is the effort per letter engraved on the stamp. The string is the text to complete.
|
| 4 | 47 | No additional constraints. |
In the third test case, an ana stamp can start at positions and , covering positions through . Position receives a twice. Writing the remaining first letter b by hand gives a total effort of .
In the first test case, create a one-letter a stamp once and use it six times. Only the creation cost of is needed.
In the second test case, create an abcd stamp and use it once. The effort is .
In the third test case, either write z by hand or create and use a one-letter stamp. Both methods cost .
