I. Two Strings Attached
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Pebae has a string $$$A$$$ and Mr Blue has a string $$$B$$$, both of length $$$N$$$ (1-indexed). For a string $$$S$$$, let $$$S[i \ldots j]$$$ denote the contiguous substring from index $$$i$$$ to $$$j$$$ (inclusive).

Now they want to find all the ways their strings can be attached! Specifically, count the number of pairs $$$(i, j)$$$ with $$$1 \leq i, j \leq N$$$ such that: $$$$$$A[1 \ldots i] + B[j \ldots n] = A[j \ldots n] + B[1 \ldots i]$$$$$$.

Here, $$$+$$$ denotes string concatenation. Please help them find the number of valid pairs.

Input

The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 10^5$$$) — the number of test cases.

The first line of each test case contains an integer $$$N$$$ ($$$1 \leq N \leq 3 \times 10^5$$$) — the length of both strings.

The second line contains a string $$$A$$$ of length $$$N$$$ consisting of lowercase English letters.

The third line contains a string $$$B$$$ of length $$$N$$$ consisting of lowercase English letters.

It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$3 \times 10^6$$$.

Output

For each test case, output a single integer — the number of valid pairs.

Example
Input
2
3
aba
bab
6
ababca
ababca
Output
4
2
Note

In the first test case, $$$A = \texttt{aba}$$$ and $$$B = \texttt{bab}$$$. The valid pairs $$$(i, j)$$$ are:

  • $$$(1, 1)$$$: $$$A[1 \ldots 1] + B[1 \ldots 3] = \texttt{a} + \texttt{bab} = \texttt{abab}$$$ and $$$A[1 \ldots 3] + B[1 \ldots 1] = \texttt{aba} + \texttt{b} = \texttt{abab}$$$
  • $$$(1, 3)$$$: $$$A[1 \ldots 1] + B[3 \ldots 3] = \texttt{a} + \texttt{b} = \texttt{ab}$$$ and $$$A[3 \ldots 3] + B[1 \ldots 1] = \texttt{a} + \texttt{b} = \texttt{ab}$$$
  • $$$(3, 1)$$$: $$$A[1 \ldots 3] + B[1 \ldots 3] = \texttt{aba} + \texttt{bab} = \texttt{ababab}$$$ and $$$A[1 \ldots 3] + B[1 \ldots 3] = \texttt{aba} + \texttt{bab} = \texttt{ababab}$$$
  • $$$(3, 3)$$$: $$$A[1 \ldots 3] + B[3 \ldots 3] = \texttt{aba} + \texttt{b} = \texttt{abab}$$$ and $$$A[3 \ldots 3] + B[1 \ldots 3] = \texttt{a} + \texttt{bab} = \texttt{abab}$$$