Ms. Thomas is managing her class of n students.
She placed all her students in a line, and gave the ith student from the left a card with the letter ai written on it. She would now like to rearrange the students so that the ith student from the left has a card with the letter bi written on it. To do this, she will choose some consecutive group of students, and reverse their order. Students will hold on to their original cards during this process.
She’s now wondering, what is the number of valid ways to do this? (It may be impossible, in which case, the answer is zero).
On the first line is an integer which gives the number of test cases. Following are is two lines of lowercase letters, A and B. The ith character of A and B represent ai and bi respectively. It is guaranteed that A and B have the same positive length, and A and B are not identical. The common length is allowed to be as large as 100000.
For each test case, output a single integer, the number of ways Ms. Thomas can reverse some consecutive group of A to form the line specified by string B.
3 abba aabb caxcab cacxab a z
1 2 0