You’re given strings A and B.
Your task is to find 3 numbers:
1. count of non-empty palindromes p such that f(A, p) > f(B, p);
2. count of non-empty palindromes p such that f(A, p) = f(B, p) and f(A, p) ≠ 0;
3. count of non-empty palindromes p such that f(A, p) < f(B, p),
where f(A, p) = count of occurrences p into A.
The first line contains T that is the number of tests to follow.
The next 2T lines contain strings A and B for each test.
The length of A and B will not exceed 200 000.
It is guaranteed that the size of input data doesn't exceed 8 MB.
For each test i print “Case #i: x y z” on a separate line where x, y and z are the three numbers to compute.
Case #1: 4 1 2
Case #2: 8 3 9
Case #3: 13 0 15
Problem Author: Mikhail Rubinchik
Problem Source: Palindromic Contest, July 11, 2015