Problem O

"A key signature is not the same as a key; key signatures are merely notational devices. They are convenient principally for diatonic or tonal music. Some pieces that change key (modulate) insert a new key signature on the staff partway, while others use accidentals: natural signs to neutralize the key signature and other sharps or flats for the new key."

-- Wikipedia

You see, key signatures can be really confusing at times. For example, consider the follow score, whose key signature is "0 sharp/flat" (which usually indicates C major/A minor):

(In ASCII format: B #C #D E #F #G #A B)

It's more reasonable to rewrite the score in the key signature "5 sharp" (which usually indicates B major/g# minor):

(In ASCII format: B C D E F G A B)

This is more "natural" because no accidentals (i.e. sharp/flat/natural sign) exist.

Given a music piece with a key signature, your task is the find the best key signature that minimizes the number of accidentals. Under that condition, the number of sharps/flats in the key signature should be minimized. Note that you CANNOT change the staff position of any note. For example, you can't change #G to bA even if this can save accidentals.

To simplify this problem, we only consider sharp, flat and natural accidentals (no double accidentals or half-sharps etc), and all the notes are in the same octave. No notes will be tied to the same note across the barline.

In your optimized score, no courtesy or cautionary accidental should be placed by a note whose pitch is, strictly speaking, already given by the key signature. However, in the original piece, such accidentals might exist to make people's life easier, because even musicians may sometimes get confused when reading the score at speed.

Important notes:

• Don't forget the effect of accidental last until the end of the measure. For example, the measure bA A A A contains only one accidental, but the last three notes are also affected, so all four notes are of the same pitch.
• The effect of the accidental has to be understood in relation to the "natural" meaning of the note's staff position, so in the key signature with 3 sharps, a bG note is actually TWO semitones lower than G (which is actually #G, thanks to the key signature).

Input

The first line contains the number of test cases T(T<=100). Each test case begins with the initial key signature formatted as "m#/b", that means the key signature has m sharps/flats (0<=m<=7). If m=0, then the #/b part is omitted. The next line contains the notes, separated by barlines '|' and ending with a double barline "||". Consecutive notes and barlines are separated by a single space. Each note is formatted as two characters, where the first is either empty or one of #(sharp), b(flat) or n(natural), the second character is one of C,D,E,F,G,A,B (upper-case). There will be at most 10 measures and 100 notes in each score.

Output

For each test case, print the minimum number of accidentals in the first line, and then the best key signatures having the least number of sharps/flats, in the same format as the input. Key signatures should be sorted lexicographically. Print a blank line after each test case.

Sample Input

4
0
C D E #F G | A B C ||
1b
F F bB B | B B #F F bD ||
7#
C D bE E F bG | G A bB ||
0
#F #C bB bE ||

Output for the Sample Input

Case 1: 0
1#

Case 2: 1
4b

Case 3: 3
5#

Case 4: 2
2# 2b

Appendix

Staff. In standard Western musical notation, the staff, or stave, is a set of five horizontal lines and four spaces that each represent a different musical pitch.

See: http://en.wikipedia.org/wiki/Staff_%28music%29

Key signature. A key signature is a series of sharp or flat symbols placed on the staff, designating notes that are to be consistently played one semitone higher or lower than the equivalent natural notes unless otherwise altered with an accidental...

See: http://en.wikipedia.org/wiki/Key_signature

Accidentals. An accidental is a note whose pitch (or pitch class) is not a member of a scale or mode indicated by the most recently applied key signature ...In most cases, a sharp raises the pitch of a note one semitone while a flat lowers it a semitone. A natural is used to cancel the effect of a flat or sharp. This system of accidentals operates in conjunction with the key signature, whose effect continues throughout an entire piece, unless canceled by another key signature. An accidental can also be used to cancel or reinstate the flats or sharps of the key signature...accidentals have been understood to continue for the remainder of the measure in which they occur, so that a subsequent note on the same staff position is still affected by that accidental, unless marked as an accidental on its own...

See: http://en.wikipedia.org/wiki/Accidental_%28music%29

Finally, looking that Circle of fifth if you're not sure about some key signatures: