Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4110
Strings in the Pocket

Time Limit: 1 Second      Memory Limit: 65536 KB

BaoBao has just found two strings $s = s_1s_2\dots s_n$ and $t = t_1t_2\dots t_n$ in his left pocket, where $s_i$ indicates the $i$-th character in string $s$, and $t_i$ indicates the $i$-th character in string $t$.

As BaoBao is bored, he decides to select a substring of $s$ and reverse it. Formally speaking, he can select two integers $l$ and $r$ such that $1 \le l \le r \le n$ and change the string to $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$.

In how many ways can BaoBao change $s$ to $t$ using the above operation exactly once? Let $(a, b)$ be an operation which reverses the substring $s_as_{a+1} \dots s_b$, and $(c, d)$ be an operation which reverses the substring $s_cs_{c+1} \dots s_d$. These two operations are considered different, if $a \ne c$ or $b \ne d$.

Input

There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains a string $s$ ($1 \le |s| \le 2 \times 10^6$), while the second line contains another string $t$ ($|t| = |s|$). Both strings are composed of lower-cased English letters.

It's guaranteed that the sum of $|s|$ of all test cases will not exceed $2 \times 10^7$.

Output

For each test case output one line containing one integer, indicating the answer.

Sample Input

2
abcbcdcbd
abcdcbcbd
abc
abc

Sample Output

3
3

Hint

For the first sample test case, BaoBao can do one of the following three operations: (2, 8), (3, 7) or (4, 6).

For the second sample test case, BaoBao can do one of the following three operations: (1, 1), (2, 2) or (3, 3).


Author: WENG, Caizhi
Source: The 16th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple
Submit    Status