AT_abc462_f [ABC462F] More ABC

给定一个仅包含大写英文字母的字符串 $S$。 高桥的目标是：通过替换 $S$ 中若干个字符，将 $S$ 中 $\texttt{ABC}$ 子串的出现次数**增加** $K$ 次。 判断这是否可行。如果可行，求出至少要替换多少字符。 有 $T$ 组测试数据，解决每一个。 :::info[什么是替换？] 替换 $S$ 中一个字符，即选择一个整数 $1 \le i \le |S|$，然后将 $S$ 的第 $i$ 个字符替换为任意一个**大写**英文字母。 这里，$|S|$ 为 $S$ 的长度。 ::: :::info[什么是子串？] $S$ 的子串是通过删除 $S$ 开头或结尾若干的字符得到的字符串。 如果两个子串被取出的位置不同，则它们不同，尽管它们本质相同。 :::

按照以下格式从标准输入读入： > $T$ > $\mathrm{case}_1$ > $\mathrm{case}_2$ > $\vdots$ > $\mathrm{case}_T$ $\mathrm{case}_i$ 为第 $i$ 组测试数据。 每组测试数据的格式如下： > $S$ > $K$

输出 $T$ 行。 第 $i$ 行 $(1 \le i \le T)$ 需要包含第 $i$ 组测试数据的答案。 对于每组测试数据，如果不能达成高桥的目标，输出 $-1$，否则输出最少替换次数。

### 样例 1 解释 对于第一组测试数据，给定的字符串 $S=\texttt{ATCABC}$ 有 $1$ 个 $\texttt{ABC}$ 子串。 将 $S$ 的第二个字符替换为 $\tt B$，得到 $S=\texttt{ABCABC}$，包含 $2$ 个 $\texttt{ABC}$ 子串。 所以，替换 $1$ 个字符会使得 $S$ 的 $\texttt{ABC}$ 子串数量增加 $1$，达成了目标。所以在第一行输出 $1$。 对于第二组测试数据，给定的字符串 $S=\texttt{ABABC}$ 有 $1$ 个 $\texttt{ABC}$ 子串。无论如何替换 $S$ 中的字符，都不能使得 $S$ 出现 $2$ 个 $\texttt{ABC}$ 子串。 所以，在第二行输出 $-1$。 对于第三组测试数据，给定的字符串 $S=\texttt{XABCYZ}$ 有 $1$ 个 $\texttt{ABC}$ 子串。 为了使得 $S$ 包含 $2$ 个 $\texttt{ABC}$ 子串，$S$ 中所有字符均需要被替换，得到 $S=\texttt{ABCABC}$。 所以，在第三行输出 $6$。 #### 数据范围 + $1 \le T \le 10^5$ + $S$ 的长度在 $[3,3 \times 10^5]$ 之间，只包含大写英文字母。 + $1 \le K \le 10$ + 输入中所有测试数据的 $S$ 的总长不超过 $3 \times 10^5$。 + $T,K$ 为整数。