给你两个非空字符串 $$$s$$$ 和 $$$t$$$,由拉丁字母组成。
在一步操作中,您可以选择字符串 $$$s$$$ 中出现的字符串 $$$t$$$ 并将其替换为点。
你的任务是在最小步数中删除字符串 $$$s$$$ 中所有出现的字符串 $$$t$$$,并计算存在多少个不同的最小长度的移动序列。
如果 $$$s$$$ 中删除的字符串 $$$t$$$ 开始出现的索引集不同,则认为两个移动序列不同。例如,集合 $$$\{1, 2, 3\}$$$ 和 $$$\{1, 2, 4\}$$$ 被视为不同,集合 $$$\{2, 4, 6\}$$$ 和 $$$\{2, 6\}$$$ — 也被视为不同,但集合 $$$\{3, 5\}$$$ 和 $$$\{5, 3\}$$$ — 则不然。
例如,让字符串 $$$s =$$$ "abababacababa" 和字符串 $$$t =$$$ "aba"。我们可以通过删除第 $$$3$$$ 和第 $$$9$$$ 位置出现的字符串 $$$t$$$ 来删除 $$$2$$$ 移动中所有出现的字符串 $$$t$$$。在本例中,字符串 $$$s$$$ 是“ab...bac...ba”形式的示例。还可以在第 $$$3$$$ 和第 $$$11$$$ 位置处删除字符串 $$$t$$$ 的出现。有两种不同的最小长度移动序列。
由于答案可能很大,因此输出它对 $$$10^9 + 7$$$ 取模。
输入
输入的第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 50$$$) — 测试用例的数量。各组的描述如下。
每组的第一行包含一个由小写拉丁字母组成的非空字符串 $$$s$$$ ($$$1 \le |s| \le 500$$$)。
每组的第二行包含一个由小写拉丁字母组成的非空字符串 $$$t$$$ ($$$1 \le |t| \le 500$$$)。
保证所有测试用例的字符串长度 $$$s$$$ 的总和不超过 $$$500$$$。同样,保证所有测试用例的字符串长度 $$$t$$$ 的总和不超过 $$$500$$$。
输出
对于每个测试用例,打印两个整数 - 最小移动次数和不同最佳序列的数量,以 $$$10^9 + 7$$$ 为模。
示例
输入 #1
8 abababacababa aba ddddddd dddd xyzxyz xyz abc abcd abacaba abaca abc def aaaaaaaa a aaaaaaaa aa
输出 #1
2 2 1 4 2 1 0 1 1 1 0 1 8 1 3 6
注意
第一个测试用例在语句中进行了解释。
在第二种情况下,删除四个出现中的任何一个就足够了。
在第三种情况下,字符串 $$$s$$$ 是两个字符串 $$$t =$$$ "xyz" 的串联,因此存在唯一的 $$$2$$$ 移动的最佳序列。
在第四种和第六种情况中,字符串 $$$s$$$ 最初不包含字符串 $$$t$$$ 的出现。
在第五种情况中,字符串 $$$s$$$ 恰好包含字符串 $$$t$$$ 的一次出现。