在完成家庭作业后，我们的出题人 Federmann 决定上网消磨时间。他发现了一个讨论程序设计竞赛的聊天室。Federmann 已经加入过许多类似的聊天室，但这个聊天室很特别。他一进入聊天室，就注意到有一条公告写着：“禁止发布无关话题！”Federmann 觉得这很不寻常，于是他决定坐下来参与讨论。在观察了一会儿人们讨论各种编程挑战后，他发现了一条有趣的留言：“不，Federmann 今年不会再出字符串相关的题目了。”
“哦，你们为什么会这么想呢？”Federmann 微笑着说，“难道他们不知道我的 Edward number 是 3 吗？”
随后，他思考了一些关于回文的问题：给定两个字符串 $A$ 和 $B$，它们有多少个公共回文子串？两个字符串之间的公共回文子串数量定义为满足以下条件的四元组 $(p, q, s, t)$ 的数量：
- $1 \le p, q \le length(A)$，$1 \le s, t \le length(B)$，$p \le q$ 且 $s \le t$。其中 $length(A)$ 表示字符串 $A$ 的长度。
- $A_{p..q} = B_{s..t}$
- $A_{p..q}$ 是回文串。（回文串是指正读和反读都相同的字符串）
例如，对于字符串 aba 和 ababa，$(1, 3, 1, 3)$ 和 $(1, 3, 3, 5)$ 都被视为有效的公共回文子串。
Federmann 对他的新任务感到兴奋，但他太懒了，不想写题解，请帮帮他。
输入格式
输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 组测试用例。对于每个测试用例，第一行包含字符串 $A$，第二行包含字符串 $B$。$A$ 和 $B$ 的长度均不超过 $200000$。
保证输入文件小于 $8$ MB。
输出格式
对于每个测试用例，输出一行 “Case #x: y”，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 $A$ 和 $B$ 的公共回文子串数量。
样例
样例输入 1
3 abacab abccab faultydogeuniversity hasnopalindromeatall abbacabbaccab youmayexpectedstrongsamplesbutnow
样例输出 1
Case #1: 12 Case #2: 20 Case #3: 18