Guitar is the most popular musical instrument in the world. There are some relation between notes and chords. Combinations of some notes create a chord and combining some chords create a song. When some chords make a song then the relation is created. Generally chords are expressed with some English letters. Always the sequence of chords will repeat in a circle of chords among A → B → C → D → E → F → G. To create a song at most 2 chords are essential. The relations among these some chords are generally called chord relation but I named this relation as Alphabetic Relation. My friend Anjan is a good guitarist. He wants to play the song in different chords rather playing the song in the original chords but maintains the sequence of original chords relation.

Input

All character are in uppercase (A - Z).

The first line of the input contains an integer T (0 < T < 1000) number of test cases. Two input in every test case. First input S (2 < length of S < 5000001) string that indicates the relation of original song chords and second input is character C that indicates which chord Anjan want to start the song.

Output

For each case, print the case number and the Alphabetic relation (or chord relation what you say) of C which chords Anjan wants to play. Print a blank line between test cases.

Example

Input
3
DGA
E
ABC
D
CFG
A

Output:
Case 1: EAB

Case 2: DEF

Case 3: ADE

Problem Setter: Shipu Ahamed , Dept. of CSE.

Bangladesh University of Business and Technology (BUBT)