On the game show The Last Word, the host begins a round by showing the contestant a string S of uppercase English letters. The contestant has a whiteboard which is initially blank. The host will then present the contestant with the letters of S, one by one, in the order in which they appear in S. When the host presents the first letter, the contestant writes it on the whiteboard; this counts as the first word in the game (even though it is only one letter long). After that, each time the host presents a letter, the contestant must write it at the beginning or the end of the word on the whiteboard before the host moves on to the next letter (or to the end of the game, if there are no more letters).

For example, for S = CAB, after writing the word Con the whiteboard, the contestant could make one of the following four sets of choices:

• put the A before C to form AC, then put the B before AC to form BAC
• put the A before C to form AC, then put the B after AC to form ACB
• put the A after C to form CA, then put the B before CA to form BCA
• put the A after C to form CA, then put the B after CA to form CAB

The word is called the last word when the contestant finishes writing all of the letters from S, under the given rules. The contestant wins the game if their last word is the last of an alphabetically sorted list of all of the possible last words that could have been produced. For the example above, the winning last word is CAB(which happens to be the same as the original word). For a game with S = JAM, the winning last word is MJA.
You are the next contestant on this show, and the host has just showed you the string S. What's the winning last word that you should produce?

Input
The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line with a string S.

Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and yis the winning last word, as described in the statement

Limits
1 ≤ T ≤ 100.
Small dataset
1 ≤ length of S ≤ 15. Large dataset
1 ≤ length of S ≤ 1000.

Sample

Input	Output
7
CAB	Case #1: CAB
JAM	Case #2: MJA
CODE	Case #3: OCDE
ABAAB	Case #4: BBAAA
CABCBBABC	Case #5: CCCABBBAB
ABCABCABC	Case #6: CCCBAABAB
ZXCASDQWE	Case #7: ZXCASDQWE

Solution in J lang:

---

#!/usr/bin/env jconsole

NB. convert string to decimal
atoi=: 10"_#. '0123456789'"_ i. ]

NB. compute ASCII code for given letter
alphabet=: 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ascii=: 3 : 0
    65 &+ alphabet i. y
)

NB. compute the last word
last_word=: 3 : 0
    NB. take first character from the given word and push front
    head=. 0 { y
    result=. head , ''

    NB. loop all rest characters in the given word
    i=. 1
    while. i ~: #y do.
        NB. take i-th letter
        letter=. i { y

        NB. push front if its ASCII code is equal to or greater
        NB. than the first letter we've handled
        if. (ascii letter) >: (ascii head) do.
            head=. letter
            result=. letter , result
        else.
            result=. result , letter
        end.
        i=. >: i
    end.
    result
)

NB. Handle case
case=: 3 : 0
    NB. convert the number of cases into decimal
    count=: atoi > 0 { y
    current=: 0
    while. current ~: count do.
        NB. take input, compute and print
        current=: >: current
        data=: current { y
        result=: last_word > data
        echo ; ":&.> 'Case #' ; current ; ': ' ; result
    end.
)

NB. get data and handle them
] input=: <;._1 LF , stdin ''
case input
exit 0