ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

2059. Not common palindromes

Time limit: 1.0 second
Memory limit: 64 MB
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.

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