Ayla has two strings and , each of length , and each of which is made of uppercase English alphabet letters. She would like to know how many different substrings of appear as anagrammatic substrings of . More formally, she wants the number of different ordered tuples , with , such that the -th through -th characters of (inclusive) are the same multiset of characters as at least one contiguous substring of length in .
输入格式
The first line of the input gives the number of test cases, . test cases follow. Each test case starts with one line, containing : the length of the string. The next two lines contain one string of characters each: these are strings and , in that order.
输出格式
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the answer Ayla wants, as described above.
样例
样例输入 1
6
3
ABB
BAB
3
BAB
ABB
6
CATYYY
XXXTAC
9
SUBXXXXXX
SUBBUSUSB
4
AAAA
AAAA
19
PLEASEHELPIMTRAPPED
INAKICKSTARTFACTORY
样例输出 1
Case #1: 5
Case #2: 6
Case #3: 6
Case #4: 6
Case #5: 10
Case #6: 9
数据范围与提示
In Sample Case #1, , = ABB, and = BAB There are 6 substrings of :
A. The substring A in is (trivially) an anagram.
B. The substring B in is (trivially) an anagram.
B. The substring B in is (trivially) an anagram.
AB. The substring AB in is (trivially) an anagram.
BB. There is no corresponding anagrammatic substring in .
ABB. The substring BAB in is an anagram.
In total, there are 5 substrings with a corresponding anagrammatic substring in , so the answer is 5.
In Sample Case #2, note that it is the same as Sample Case #1, except that and are swapped. This changes the answer to 6!
In Sample Case #3, note that the substring CAT in has the corresponding substring TAC in which is an anagram. This still counts, even though the strings are at different indices in their respective strings.
In Sample Case #4, note that although the substring SUB in has several corresponding substrings in which are anagrams, it only counts once.
In Sample Case #5, note that every substring of has a corresponding anagrammatic substring in , so the answer is 10.
Limits
.
.
Small dataset (Test set 1 - Visible)
The two strings and will consist only of the characters A and B.
