Description

输入包含多组测试数据,第一行为一个整数T,代表总测试数.
接下来一行为一个整数n,代表房间总数.
接下来一行为一个长度为n的01串s,代表刚开始你有的钥匙,si为1代表有第i个房间的钥匙,0代表没有。
接下来n行代表,你进入第i个房间之后可以获得的钥匙,同理串第i个位置的1/0代表你可以是否获得第i个位置的钥匙

Format

Input

第一行一个数字T，T<=50
接下来T组数据
每组数据第一行为n代表n个房间(n<=18)
接下来第一行为初始的钥匙状态
然后有n行代表进入第i个房间你能获得的钥匙

Output

T行，每行格式：
Case i: ans

Sample 1

Input

3 
1 
1 
1
2 
11 
01 
10 
3 
110
011 
100 
000

Output

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

Limitation

1s, 1024KiB for each test case.