生物学家最近在某种生物中发现了一种有趣的现象。每种生物都拥有一条仅由 A 和 B 两种基因组成的基因序列。
这些生物进行无性繁殖，这意味着后代通常会继承完全相同的基因序列。然而，由于繁殖过程中偶尔会出现克隆错误，可能会发生突变。生物学家观察到这些错误可以采取以下形式：
- 在基因序列的任意位置插入子串 AA。
- 从基因序列的任意位置移除子串 AA；剩余部分按原顺序连接。
- 在基因序列的任意位置插入子串 BBB。
- 从基因序列的任意位置移除子串 BBB；剩余部分按原顺序连接。
- 在基因序列的任意位置插入特殊子串 $s$。
- 从基因序列的任意位置移除子串 $s$；剩余部分按原顺序连接。
这些突变在单次克隆事件中可能会发生多次，且总是按顺序逐一发生。
例如，假设 $s = \text{ABAB}$。基因序列为 $\text{ABBABBA}$ 的生物可以通过以下一系列突变产生基因序列为 $\text{A}$ 的后代：
生物学家拥有一个基因序列为 $t$ 的生物。他们还对所有基因序列长度为 $n$ 的可能生物感兴趣。由于基因序列的每个位置都可以是 A 或 B，因此总共有 $2^n$ 种这样的生物。
问题是：给定字符串 $s$、$t$ 和 $n$，在这些 $2^n$ 种生物（即所有长度为 $n$ 的基因序列）中，有多少种可以通过上述有效突变操作序列从基因序列为 $t$ 的生物产生？
由于答案可能非常大，请输出结果对 998244353 取模后的值。
输入格式
每个测试包含多个测试用例。第一行包含测试用例的数量 $q$。接下来是各测试用例的描述。
第一行包含字符串 $s$，表示特殊子串。 第二行包含字符串 $t$，表示给定的基因序列。 第三行包含整数 $n$，表示感兴趣的生物基因序列长度。
- $1 \le q \le 10$
- $2 \le |s| \le 11$
- $s$ 的第一个字符是 A。
- $s$ 的最后一个字符是 B。
- $s$ 中不存在两个连续的 A。
- $s$ 中不存在三个连续的 B。
- $1 \le |t| \le 10^5$
- $1 \le n \le 10^9$
输出格式
对于每个测试用例，输出一行一个整数，表示答案对 998244353 取模的结果。
样例
输入 1
2 ABAB AABAB 1 ABAB A 7
输出 1
1 22