공통 애너그램

Ayla는 길이가 L이고 모두 대문자 영어 알파벳으로 이루어진 두 문자열 A와 B를 가지고 있다. 그녀는 A의 서로 다른 부분 문자열 중 B의 애너그램 부분 문자열로 나타나는 것이 몇 개인지 알고 싶어 한다. 더 형식적으로는, 0 ≤ i ≤ j < L이고 A의 i번째부터 j번째 문자까지(양 끝 포함)가 B의 길이 (j - i + 1)인 어떤 연속 부분 문자열과 같은 문자 집합(multiset)을 이루는 서로 다른 순서쌍 (i, j)의 개수를 구하려 한다.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스는 한 줄에 L이 주어지고, 그다음 두 줄에 각각 길이 L인 문자열이 하나씩 주어지는데, 이는 순서대로 문자열 A와 B이다.

각 테스트 케이스마다 한 줄에 Case #x: y를 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 위에서 설명한 Ayla가 원하는 답이다.

• 1 ≤ T ≤ 100.
• 1 ≤ L ≤ 50.

예제 1에서 L = 3, A = ABB, B = BAB이다. A의 부분 문자열은 6개다:

• A. B의 부분 문자열 A는 (자명하게) 애너그램이다.
• B. B의 부분 문자열 B는 (자명하게) 애너그램이다.
• B. B의 부분 문자열 B는 (자명하게) 애너그램이다.
• AB. B의 부분 문자열 AB는 (자명하게) 애너그램이다.
• BB. B에 대응하는 애너그램 부분 문자열이 없다.
• ABB. B의 부분 문자열 BAB는 애너그램이다.

B에 대응하는 애너그램 부분 문자열이 있는 부분 문자열은 모두 5개이므로 답은 5이다.

예제 2는 예제 1과 A와 B만 바뀐 것이고, 답은 6으로 달라진다.

예제 3에서 A의 부분 문자열 CAT은 B의 부분 문자열 TAC과 애너그램 관계이다. 두 문자열의 위치가 각각 다르더라도 이는 인정된다.

예제 4에서 A의 부분 문자열 SUB은 B에 애너그램 관계인 부분 문자열이 여러 개 있지만, 한 번만 센다.

예제 5에서 A의 모든 부분 문자열은 B에 대응하는 애너그램 부분 문자열이 있으므로 답은 10이다.