熊猫先生拥有许多仅由大写字母组成的字符串。他将字符串的“幸福度”定义为该字符串中 “SAD”（SAD 代表上海算法讨论，Shanghai Algorithm Discussion）出现的次数。

有一天，熊猫先生不小心把他的一条珍贵字符串弄成了 $n$ 个碎片。第 $i$ 个碎片上写着字符串 $s_i$。他收集了所有碎片并向羊先生求助。由于熊猫先生对弄坏字符串感到非常难过，羊先生安慰他说，如果他们把所有碎片拼接成一个新的字符串，这个字符串的幸福度甚至可能比原来的幸福度还要高！但他们确实不知道如何拼接这些碎片才能获得最大的幸福度。现在轮到你来帮助他们了。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。接下来是 $T$ 个测试用例。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 2 \times 10^5$)，表示熊猫先生的珍贵字符串被拆分成的碎片数量。

接下来的 $n$ 行，每行包含一个仅由大写字母组成的字符串 $s_i$ ($1 \le |s_i| \le 20$)。

保证所有测试用例中 $n$ 的总和不超过 $10^6$，且所有测试用例中 $|s_i|$ 的总和不超过 $2 \times 10^6$。

输出格式

对于每个测试用例，输出一行 “Case #x: y”，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是通过拼接碎片所能达到的最大幸福度。

样例

样例输入 1

3
3
SAD
D
SA
3
SS
A
DD
4
DS
SA
ADSA
D

样例输出 1

Case #1: 2
Case #2: 1
Case #3: 3

说明

对于第一个样例，新字符串可以拼接为 SADSAD，因此幸福度为 2。

对于第二个样例，新字符串可以拼接为 SSADD，因此幸福度为 1。

对于第三个样例，新字符串可以拼接为 SA+DS+ADSA+D = SADSADSAD，因此幸福度为 3。