描述

鼹鼠是一种奇特的哺乳动物，适应地下生活方式。它的眼睛不易察觉，四肢短小而有力，爪子较大，适合挖掘。

在灾难性地震发生前，一群鼹鼠察觉到了这场灾难。它们迁移到一个安全的地方，并想在地下挖洞。这里有$n$只鼹鼠，编号从$1$到$n$。它们排成一排，一只接一只地挖洞。鼹鼠的排列顺序不一定是按编号排序的。每只鼹鼠都应该住在自己挖的洞里，并且每只鼹鼠只挖一个洞。队伍中的第一只鼹鼠挖第一个洞，并挖一条通向地面的通道。然后其他鼹鼠通过这条通道下去，挖掘更多的洞和通道。一个洞最多可以有三个相邻的洞通过通道相连，一个在更高一层，另外两个洞在更低一层，分别位于左侧和右侧。当一只鼹鼠到达一个洞时，如果它的编号小于这个洞的主人的编号，它将前往左下方的洞（如果没有左下方的洞，则挖一个左下方的洞并待在那里），否则它将前往右下方的洞（如果没有右下方的洞，则挖一个右下方的洞并待在那里）。由于出色的能力和精心设计的布局，这些洞和通道不会相互交叉。

老鼠杰瑞是这些鼹鼠的朋友。他来看望它们，并为每只鼹鼠准备了礼物。有一个规则，编号较小的鼹鼠必须比编号较大的鼹鼠更早收到礼物。杰瑞从地面出发。他穿过这些洞和通道去送礼物。在送出所有礼物后，他回到地面。在鼹鼠的世界里，有趣的是编号为奇数的鼹鼠是雄性，其他的是雌性。当到达一个洞时，杰瑞会记录下这个洞主人的性别（$0$表示雌性，$1$表示雄性）。当他回到地面时，他会得到一个$0-1$序列。现在他想计算“和谐值”。和谐值表示给定的“和谐字符串”在上述序列中出现的次数。出现的情况可能会重叠。

请注意，杰瑞非常聪明，所以他的行走距离尽可能短。

输入

第一行包含一个整数$t$，表示有$t$个测试用例（$t \leq 10$）。

对于每个测试用例：

第一行是一个整数$n$，表示有$n$只鼹鼠。（$n \leq 600000$）。

第二行包含$n$个整数，表示鼹鼠的队伍顺序。每个整数是一只鼹鼠的编号，并且第一个整数是队伍中第一只鼹鼠的编号。

第三行是和谐字符串。字符串长度不超过$7000$。

输出

对于每个测试用例，请输出用例编号和和谐值。

输入数据 1

2
8
5 1 3 2 7 8 4 6
01
10
1 2 3 4 5 6 7 8 9 10
1010

输出数据 1

Case #1: 4
Case #2: 8

提示

在第一个测试用例中，第一个用例的$0-1$序列是“$111010111101011$”，和谐字符串“$01$”出现的次数是$4$。

来源

2011年福州赛