AT_abc462_f.More ABC

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.

给你一个由大写英文字母组成的字符串 $S$。
高桥的目标是通过替换 $S$ 中的某些字符，恰好增加 $S$ 中子串 ABC 的出现次数 $K$ 次。

请判断该目标是否可行；若可行，求出高桥为达成目标所需替换的最少字符数。

共给出 $T$ 组测试数据，请对每组数据求解。

什么是“替换”？

替换 $S$ 中的一个字符，是指选择一个满足 $1\leq i\leq \lvert S\rvert$ 的整数 $i$，并将 $S$ 的第 $i$ 个字符替换为任意一个大写英文字母。
其中，$\lvert S\rvert$ 表示字符串 $S$ 的长度。

什么是子串？

字符串 $S$ 的一个子串，是指从 $S$ 的开头和结尾分别删去零个或多个字符后所得的字符串。
即使两个子串作为字符串相等，只要它们在 $S$ 中起始位置不同，就视为不同的子串。

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$

输入从标准输入给出，格式如下：

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

$\mathrm{case}_i$ 表示第 $i$ 个测试用例。
每个测试用例的格式如下：

$S$
$K$

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.

输出 $T$ 行。
第 $i$ 行（$1\leq i\leq T$）应包含第 $i$ 个测试用例的答案。
对于每个测试用例，若高桥无法实现其目标，则输出 $-1$；否则，输出为实现其目标所需替换的最少字符数。

Sample 1 Explanation:
In the first test case, the given string $S=$ATCABC contains ABC as a substring once.
Replacing the second character of $S$ with B gives $S=$ABCABC, which contains ABC as a substring twice.
Thus, replacing one character increases the number of occurrences of ABC as a substring by $1$, achieving the goal. Therefore, output $1$ on the first line.

In the second test case, the given string $S=$ABABC contains ABC as a substring once; no matter how the characters of $S$ are replaced, it is impossible to make $S$ contain ABC as a substring twice.
Therefore, output $-1$ on the second line.

In the third test case, the given string $S=$XABCYZ contains ABC as a substring once.
To make $S$ contain ABC as a substring twice, all characters of $S$ must be replaced, giving $S=$ABCABC.
Therefore, output $6$ on the third line.

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.

样例 1 解释：
在第一个测试用例中，给定字符串 $S=$ATCABC 包含子串 ABC 恰好一次。
将 $S$ 的第二个字符替换为 B，得到 $S=$ABCABC，该字符串包含子串 ABC 两次。
因此，仅需替换一个字符，即可使子串 ABC 的出现次数增加 $1$，从而达成目标。故第一行输出 $1$。

在第二个测试用例中，给定字符串 $S=$ABABC 包含子串 ABC 恰好一次；无论怎样替换 $S$ 中的字符，都不可能使 $S$ 包含子串 ABC 两次。
因此，第二行输出 $-1$。

在第三个测试用例中，给定字符串 $S=$XABCYZ 包含子串 ABC 恰好一次。
为使 $S$ 包含子串 ABC 两次，必须替换 $S$ 的所有字符，得到 $S=$ABCABC。
因此，第三行输出 $6$。

约束条件

• $1\leq T\leq 10^5$
• $S$ 是一个长度在 $3$ 到 $3\times 10^5$（含）之间的字符串，仅由大写英文字母组成。
• $1\leq K \leq 10$
• 在每组输入中，所有测试用例的 $S$ 的总长度不超过 $3\times 10^5$。
• $T$ 和 $K$ 均为整数。