글 쓰기

다다스는 영어 소문자로 이루어진 길이 $N$의 글 $s$를 완성하려고 한다. 처음에는 $N$개의 위치가 모두 비어 있다. 글자 하나를 직접 쓰는 데에는 $A$만큼의 힘이 든다.

글을 쓰는 수고를 줄이기 위해, 다다스는 원하는 문자열이 새겨진 도장을 하나 만들 수 있다. 도장에 새길 문자열의 길이가 $x$ $(1\leq x\leq N)$라면, 도장을 만드는 데에는 $xB$만큼의 힘이 든다. 도장을 만들지 않아도 되지만, 만든다면 한 종류만 만들 수 있다.

도장은 다음과 같이 사용한다.

• 도장에 새겨진 문자열과 정확히 같은 문자열이 들어가야 하는 연속한 $x$개의 위치에 도장을 찍을 수 있다. 도장 전체가 글의 범위 안에 들어가야 한다.
• 도장을 한 번 찍으면 해당 위치들에 도장의 글자가 모두 적힌다. 도장을 찍는 데에는 힘이 들지 않으며, 같은 도장을 몇 번이든 사용할 수 있다.
• 이미 글자가 적힌 위치에 다시 찍어도 된다. 다만 그 위치에 적혀야 하는 글자와 같은 글자를 찍어야 한다.

예를 들어, 글이 abcabca이고 도장에 abca가 새겨져 있다고 하자. 먼저 $1$번째부터 $4$번째 위치에 찍고, 다음으로 $4$번째부터 $7$번째 위치에 찍으면 글 전체를 완성할 수 있다. $4$번째 위치에는 a가 두 번 찍히지만 문제가 없다.

도장으로 채우지 않은 위치에는 글자를 직접 쓰면 된다. 다다스가 글 $s$를 완성하는 데 필요한 힘의 최솟값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

각 테스트 케이스마다 글 $s$를 완성하는 데 필요한 힘의 최솟값을 한 줄에 출력한다.

• $1\leq T\leq200\,000$.
• $1\leq N\leq200\,000$.
• $1\le A,$.