SP21396 TKUDDUS - Taklu Kuddus

Kuddus 是一名非常出色的程序员。他最近在各大在线评测系统中解决了 100 道题目。然而，有一天他的女朋友出了一道题给他，他没能解决，这让女朋友非常不满。 因此，女朋友不再愿意理他。Kuddus 因为思考如何解决这道题目而焦虑不已。现在，他来找你寻求帮助。作为他的朋友，你需要帮助 Kuddus 解决这个难题，以挽回他的爱情和头发。 题目的要求是这样的：给定一个字符串 $S$ 和一个模式串 $P$，你的任务是找到函数 $FS(x, y)$，它表示在字符串 $S$ 的从 $x$ 到 $y$ 的子串中，等同于模式串 $P$ 的非重叠子串的最大数目（$x$ 和 $y$ 均为 0 起始索引）。 例如， $S = \text{``abcdef''}$ $P = \text{``cd''}$ 如果查询是 $(1, 5)$，子串为 “b**cd**ef”，所以 $FS(1, 5) = 1$。

第一行包含一个整数 $T$，表示测试用例的数量，$1 \le T \le 10$。 每个测试用例的第一行给出字符串 $S$，满足 $|S| \le 1000000$。接下来一行给出字符串 $P$，满足 $|P| \le 1000000$。 接下来是一个整数 $q$，表示查询的数量，$1 \le q \le 100000$。接下来的 $q$ 行，每行包含两个整数 $i$ 和 $j$，表示查询区间（$0 \le i \le j < |S|$）。

对于每个测试用例，首先输出一行，显示测试用例编号。 然后针对每个查询，输出一行，给出对应的 $FS(i, j)$ 的值。

- 总的来说，每个测试用例中的所有查询数量的总和不会超过 200000。 **本翻译由 AI 自动生成**