Deep beneath the Citadel of Eternal Letters lies the Whispering Archives — a vault sealed for millennia, whose enchanted doors open only to those who can recite two simultaneous palindromic incantations.
The vault's guardian, Valdris the Scribe, inscribed its secrets across two sacred scrolls: $$$A$$$ and $$$B$$$. To unseal the vault, a supplicant must pick a split point $$$i$$$ and a meeting index $$$j$$$, then chant both of the following at once:
$$$P_1 = A[1\ldots i] + B[j\ldots |B|]$$$
$$$P_2 = B[1\ldots i] + A[j\ldots |A|]$$$
Both $$$P_1$$$ and $$$P_2$$$ must be palindromes simultaneously. Centuries of failed attempts have filled the antechamber with very flat scholars. Help the next adventurer survive by counting every valid pair $$$(i, j)$$$ such that $$$1 \leq i,j \leq |A|$$$.
The first line contains $$$T\ (1 \le T \le 10^5)$$$.
Each test case consists of two lines containing strings $$$A$$$ and $$$B$$$ of lowercase English letters, with $$$|A| = |B|$$$ ($$$1 \le |A|,|B| \le 10^6$$$).
Sum of $$$|A|+|B|$$$ over all test cases is less than $$$2 \times 10^6$$$
For each test case, a single integer — the number of valid pairs $$$(i, j)$$$.
4abacabaabacabaaaaaaaabccbaabyyycddczzzba
259710
A string $$$S$$$ of length $$$\ell$$$ is a palindrome if $$$S[k] = S[\ell - k + 1]$$$ for all $$$1 \le k \le \ell$$$. The empty string is considered a palindrome.
