A key is a string consisting of ‘E’, ‘S’, ‘W’ and ‘N’s. Some of keys are called master keys, and the others are called servant keys. Give you one master key K_M and N servant keys (S₁ to S_N). You are asked to determine what the length of the longest prefix which can be found in the master key is for every servant key.

The first line of the input gives the number of test cases T. T test cases follow.

Each test case starts with a line consist of one string representing K_M. The next line consists of one integer N. Then N lines follows. The i^th line consists of one string representing S_i.

1 ≤ |K_M| ≤ 10⁶.

1 ≤ N ≤ 10⁴.

1 ≤ |S_i| ≤ 10².

K_M and S_i consists of only ‘E’, ‘S’, ‘W’, and ‘N’.

1 ≤ the total length of all keys in one input file ≤ 4 × 10⁶.

For each test case, first output one line containing “Case #x:”, where x is the test case number.

Then for every servant key, output one line consists of one integer indicating the length of the longest prefix which can be found in the master key.

2 
SNNSSNS
3
NNSS
NNN
WSEE
NSWWEEW
3
NNSW
EEW
WWEE

Case #1:
4
2
0
Case #2:
1
3
4