BaoBao 刚刚在他的左口袋里发现了两个字符串 $s = s_1s_2 \dots s_n$ 和 $t = t_1t_2 \dots t_n$，其中 $s_i$ 表示字符串 $s$ 的第 $i$ 个字符，$t_i$ 表示字符串 $t$ 的第 $i$ 个字符。

由于 BaoBao 感到很无聊，他决定选择 $s$ 的一个子串并将其反转。形式化地说，他可以选择两个整数 $l$ 和 $r$，满足 $1 \le l \le r \le n$，并将字符串变为 $s_1s_2 \dots s_{l-1}s_rs_{r-1} \dots s_{l+1}s_ls_{r+1} \dots s_{n-1}s_n$。

BaoBao 有多少种方法可以通过上述操作恰好一次将 $s$ 变为 $t$？设 $(a, b)$ 为反转子串 $s_as_{a+1} \dots s_b$ 的操作，$(c, d)$ 为反转子串 $s_cs_{c+1} \dots s_d$ 的操作。如果 $a \neq c$ 或 $b \neq d$，则这两个操作被视为不同。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含一个字符串 $s$ ($1 \le |s| \le 2 \times 10^6$)，第二行包含另一个字符串 $t$ ($|t| = |s|$)。两个字符串均由小写英文字母组成。

保证所有测试数据的 $|s|$ 之和不超过 $2 \times 10^7$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示答案。

样例

样例输入 1

2
abcbcdcbd
abcdcbcbd
abc
abc

样例输出 1

3
3

说明

对于第一个样例，BaoBao 可以执行以下三种操作之一：$(2, 8)$，$(3, 7)$ 或 $(4, 6)$。

对于第二个样例，BaoBao 可以执行以下三种操作之一：$(1, 1)$，$(2, 2)$ 或 $(3, 3)$。