Vault Patterns

You are given a pattern string which consists only of the characters A and B. Each character in the pattern represents a range of numbers in the following manner:

• A: All integers from 1 to 10 (i.e. \(1 \le x \le 10\)).
• B: All integers from 11 to 20 (i.e. \(11 \le x \le 20\)).

Your task is to generate all possible sequences of numbers that match the given pattern. For a pattern of length \(n\), you will produce all \(n\)-tuples where each position is taken from the respective number range defined by the pattern.

After generating the sequences, solve_vault_patterns should output, for each test case, a line in the following format:

Case #x: sequence

Here, x stands for the test case number (starting at 1) and sequence represents the list of valid sequences. Each sequence is printed as numbers separated by commas and sequences are separated by a single space.

For example, if the pattern is A, the only sequences are:

1
2
3
4
5
6
7
8
9
10

For pattern AB, the sequences would be all pairs \((x,y)\) where \(x\) is drawn from \(\{1,2,\dots,10\}\) (from A) and \(y\) from \(\{11,12,\dots,20\}\) (from B). Your generated output should list these pairs in lexicographical order.

inputFormat

The input is read from standard input (stdin) and has the following format:

T
pattern_1
pattern_2
...
pattern_T

Here, T is an integer denoting the number of test cases, followed by T lines where each line is a pattern consisting of characters A and B.

outputFormat

For each test case, output a line in the following format to standard output (stdout):

Case #x: sequence

In the output, replace x with the test case number (starting at 1) and sequence with all generated valid sequences for the given pattern. Each sequence is a comma-separated list of numbers, and sequences are separated from one another by a single space.

## sample

1
A

Case #1: 1 2 3 4 5 6 7 8 9 10

</p>