32512번 - ABC

문자열 $U$에 대해 $U_k$을 $U$의 길이가 $k$인 접두사, $U_{-k}$ 을 $U$의 길이가 $k$인 접미사로 정의하자. 예를 들어 $U$=cuthere 일 경우, $U_3$=cut, $U_{-4}$=here 이다.

두 문자열 $S, T$ 에 대해서, $\text{PrefixSuffix}(S, T)$ 를 $S_{-k}=T_k$인 가장 큰 정수 $k$로 정의하자. $\text{PrefixSuffix}(S, T)$ 함수는 항상 0 이상이며, $S$의 길이와 $T$의 길이 이하임을 알 수 있다.

마지막으로, 두 문자열 $U, V$ 에 대해서, $U+V$를 $U$와 $V$를 순서대로 붙인 것으로 정의하자. 예를 들어 $U$=baek, $V$=joon 일 경우, $U+V$=baekjoon 이다.

길이 $n$의 문자열 $A$, 길이 $m$의 문자열 $B$, 문자열 $C$가 주어질 때, 다음 값을 계산하여라:

$\sum_{i = 1}^{n}\sum_{j=1}^{m} \text{PrefixSuffix}(A_i+B_j, C)$

파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 $T$ 가 주어지고,

이후 차례로 $T$ 개의 테스트 케이스가 주어진다. ($1 \le T \le 75$)

각 테스트 케이스의 첫 줄에는 문자열 A가 주어진다.

그 다음 줄에는 문자열 B가 주어진다.

그 다음 줄에는 문자열 C가 주어진다.

모든 문자열은 알파벳 소문자로만 이루어져 있으며, 그 길이가 $1$ 이상 $250\,000$ 이하이다.

전체 테스트 케이스에 대해서 모든 문자열의 길이 합은 $21\,000\,000$ 을 넘지 않는다.

각 테스트 케이스마다 첫 줄에는 Case #$C$ 를 출력하여야 한다. 이때 $C$는 테스트 케이스의 번호이다.

다음 줄에는 문제의 정답을 출력한다.