7605: 最小划分

给定一个字符串 $ S $，我们定义一个字符串 $ t $ 的 **$ k $-划分** 如下：如果 $ t $ 可以被分割成 $ k $ 个部分，且每个部分都是 $ S $ 的子串，那么我们称这是一个关于 $ t $ 的 **$ k $-划分**。 假设 $ S = \texttt{aabc} $ 和 $ t = \texttt{caba} $。我们可以将 $ t $ 分割为 $ \texttt{c} | \texttt{ab} | \texttt{a} $，其中 $ \texttt{c} $、$ \texttt{ab} $ 和 $ \texttt{a} $ 都是 $ S $ 的子串。因此，这是一个关于 $ t $ 的 **3-划分**。显然，$ t $ 还存在一个 **4-划分**：$ \texttt{c} | \texttt{a} | \texttt{b} | \texttt{a} $。 现在，给定另一个字符串 $ T $，我们需要回答关于 $ T $ 的子串的查询。对于每个查询，我们指定 $ T $ 的一个子串 $ T[l, r] $，它表示从 $ T $ 的第 $ l $ 个字符到第 $ r $ 个字符的子串。我们需要找到这个子串对于 $ S $ 的所有可能的 **$ k $-划分** 中最小的 $ k $。如果不存在这样的划分，则输出 `-1`。 **请注意，这里的字符串的下标从 $1$ 开始。** --- 为了防止输入过大带来的常数问题，`C++` 选手请尽量使用关闭流同步的 `std::cin` 和 `std::cout` 实现输入输出，否则可能出现因读入输出问题导致的 TLE 等。 ```cpp int main(){ std::ios::sync_with_stdio(0); std::cin.tie(0); // your code return 0; } ```

第一行一个整数 $ T $ $ \left(1 \leq T \leq 15\right) $，表示测试数据组数。 每组输入数据的第一行包含一个由小写字母组成的字符串 $S$ $ \left(1\leq |S| \leq 5\times 10^5\right)$。 第二行包含一个由小写字母组成的字符串 $T$ $ \left(1\leq |T| \leq 5\times 10^5\right)$。 第三行包含一个整数 $q$ $\left(1 \leq q \leq 5 \times 10^5\right)$，表示询问次数。 接下来 $q$ 行，每行包含两个用空格分隔的正整数 $l,r$ $\left(1 \leq l \leq r \leq |T|\right)$，表示一组询问。 保证所有测试数据的 $ |S| $ 之和与 $ |T| $ 之和与 $ q $ 之和均不超过 $ 10^6 $。

对于每组数据输出 $q$ 行，每行一个整数表示每个询问的答案。