ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Contest is over

## C. Not common palindromes

Time limit: 1.0 second
Memory limit: 64 MB
You’re given strings A and B.
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.

### Input

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.

### Output

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.

### Sample

inputoutput
```3
abacab
abccab
faultydogeuniversity
hasnopalindromeatall
abbacabbaccab
youmayexpectedstrongsamplesbutnow
```
```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
To submit the solution for this problem go to the Problem set: 2059. Not common palindromes