공통 애너그램

Ayla에게 각각 길이가 L이고 각각 영문 대문자로 이루어진 두 문자열 A와 B가 있다. Ayla는 A의 서로 다른 부분 문자열 중 B에 애너그램인 부분 문자열로 나타나는 것이 몇 개인지 알고 싶어 한다. 더 형식적으로 말하면, Ayla는 0 ≤ i ≤ j < L을 만족하며, A의 i번째부터 j번째까지의 문자들(양 끝 포함)이 B에 있는 길이 (j - i + 1)의 적어도 하나의 연속 부분 문자열에 포함된 문자들과 동일한 다중집합을 이루는 서로 다른 순서쌍 (i, j)의 개수를 구하고자 한다.

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 20초. 메모리 제한: 1 GB. 1 ≤ L ≤ 50.

작은 데이터 세트 (테스트 세트 1 - 공개)

두 문자열 A와 B는 A와 B 문자로만 구성된다.

큰 데이터 세트 (테스트 세트 2 - 비공개)

추가 제한은 없다.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 문자열의 길이 L이 포함된 한 줄로 시작한다. 그다음 두 줄에는 각각 L개의 문자로 이루어진 문자열 하나가 주어지며, 순서대로 문자열 A와 B이다.

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

예제 케이스 #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은 애너그램이다.

총 5개의 부분 문자열에 B의 대응하는 애너그램인 부분 문자열이 있으므로, 답은 5이다.

예제 케이스 #2은 A와 B를 서로 바꾼 것을 제외하면 예제 케이스 #1과 동일하다는 점에 유의한다. 이로 인해 답은 6로 바뀐다!

예제 케이스 #3에서 A의 부분 문자열 CAT에는 애너그램인 B의 대응하는 부분 문자열 TAC이 있다는 점에 유의한다. 두 부분 문자열이 각자의 문자열에서 서로 다른 인덱스에 있더라도 여전히 집계된다.

예제 케이스 #4에서 A의 부분 문자열 SUB에 대응하는 애너그램인 부분 문자열이 B에 여러 개 있더라도 한 번만 집계된다는 점에 유의한다.

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