Вам даны строки A и B.

Ваша задача — найти 3 числа:

1. x = количество непустых палиндромов p таких, что f(A, p) > f(B, p);
2. y = количество непустых палиндромов p таких, что f(A, p) = f(B, p) и f(A, p) ≠ 0;
3. z = количество непустых палиндромов p таких, что f(A, p) < f(B, p),
где f(A, p) = количество вхождений p в A.

Первая строка содержит число тестов T. Следующие 2T строки содержат непустые строки A и B для каждого теста. Длины A и B не превосходят 200 000. Гарантируется, что размер входных данных не превышает 8 мегабайт.

Для каждого теста i выведите «Case #i: x y z» в отдельной строке.