Niuniu has a string S of length n which only contains lowercase letters. The string will be transmitted to his best friend, Doge, in a compressed form. Niuniu would like to compress the string so that the cost is minimal. A compressed form of a string is a sequence of segments. Each segment is comprised of a number X(X ≥ 1) and a string S, which represents a new string S’=SS…S(repeated X times). Connecting the represented string of the segments in the sequence from left to right will result in the original string. Each segment costs A*|S|+B. The total cost of the compressed form is the sum of the costs of the segments in the sequence. You are asked to help Niuniu calculate the minimal cost of the compressed form. 

The first line contains one integer T(T ≤ 10), which means the number of test cases.

Each test case has two lines. The first line contains two integers A and B separated by a space. (0 ≤ A,B ≤ 1000000000) The second line contains the string S, which is the original string you have to compress.

(1 ≤ |S| ≤ 100000,  sum of |S| ≤ 550000)

For each test case，print one number in a single line, which is the minimal cost.

5
1 1
toooooooooeasy
100 1
yoooooooooooooooooooooo
1 100
yoooooooooooooooooooooo
2 1
fizzydavid
2 3
ababccdefdefdef

9
202
123
21
21

The compressed form with the minimal cost is [1,t][9,o][1,easy]
The compressed form with the minimal cost is [1,y][22,o]
The compressed form with the minimal cost is [1,yoooooooooooooooooooooo]
The compressed form with the minimal cost is [1,fizzydavid] or [1,fi][2,z][1,ydavid]
The compressed form with the minimal cost is [2,ab][2,c][3,def]