Problem Statement

You are given a string $S$ consisting of uppercase English letters. Takahashi's goal is to increase the number of occurrences of ABC as a substring of $S$ by exactly $K$, by replacing some characters of $S$.

Determine whether this is possible, and if so, find the minimum number of characters Takahashi needs to replace to achieve his goal.

$T$ test cases are given; solve each one.

What does "replacing" mean? Replacing one character of $S$ means choosing an integer $i$ satisfying $1\leq i\leq \lvert S\rvert$ and replacing the $i$-th character of $S$ with any ** one ** uppercase English letter. Here, $\lvert S\rvert$ denotes the length of $S$.

What is a substring? A substring of $S$ is a string obtained by removing zero or more characters from the beginning and end of $S$. Two substrings are counted as distinct if they are taken from different positions in $S$, even if they are equal as strings.

Constraints

• $1\leq T\leq 10^5$
• $S$ is a string of length between $3$ and $3\times 10^5$, inclusive, consisting of uppercase English letters.
• $1\leq K \leq 10$
• In each input, the total length of $S$ over all test cases is at most $3\times 10^5$.
• $T$ and $K$ are integers.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

$\mathrm{case}_i$ represents the $i$-th test case. Each test case is given in the following format:

S
K

Output

Output $T$ lines. The $i$-th line $(1\leq i\leq T)$ should contain the answer for the $i$-th test case. For each test case, if it is impossible for Takahashi to achieve his goal, output $-1$; otherwise, output the minimum number of characters that need to be replaced to achieve his goal.