13.

Nesting Depth

Given a string of digits S, insert a minimum number of opening and closing parentheses into it
such that the resulting string is balanced and each digit d is inside exactly d pairs of matching
parentheses.

Let the nesting of two parentheses within a string be the substring that occurs strictly between
them. An opening parenthesis and a closing parenthesis that is further to its right are said
to match if their nesting is empty, or if every parenthesis in their nesting matches with another
parenthesis in their nesting. The nesting depth of a position p is the number of pairs of matching
parentheses m such that p is included in the nesting of m.

For example, in the following strings, all digits match their nesting
depth: 0((2)1), (((3))1(2)), ((((4)))), ((2))((2))(1). The first three strings have minimum length among
those that have the same digits in the same order, but the last one does not since  ((22)1) also has
the digits 221 and is shorter.

Given a string of digits S, find another string S', comprised of parentheses and digits, such that:

 all parentheses in S' match some other parenthesis,

Input

The first line of the input gives the number of test cases, T. T lines follow. Each line represents a
test case and contains only the 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 y is the string S' defined above.

Limits

Time limit: 20 seconds per test set.

Sample

Input Output

0000 Case #1: 0000

101 Case #2: (1)0(1)

111000 Case #3: (111)000

1 Case #4: (1)

Someone just won the Code Jam lottery, and we owe them N jamcoins! However, when we tried
to print out an oversized check, we encountered a problem. The value of N, which is an integer,
includes at least one digit that is a 4... and the 4 key on the keyboard of our oversized check
printer is broken.

Fortunately, we have a workaround: we will send our winner two checks for positive integer
amounts A and B, such that neither A nor B contains any digit that is a 4, and A + B = N. Please help
us find any pair of values A and B that satisfy these conditions.

Input

The first line of the input gives the number of test cases, T. T test cases follow; each consists of
one line with an integer N.

Output

For each test case, output one line containing Case #x: A B, where x is the test case number
(starting from 1), and A and B are positive integers as described above.

It is guaranteed that at least one solution exists. If there are multiple solutions, you may output
any one of them. (See "What if a test case has multiple correct solutions?" in the Competing
section of the FAQ. This information about multiple solutions will not be explicitly stated in the
remainder of the 2019 contest.)

Limits

1 ≤ T ≤ 100.
Time limit: 10 seconds per test set.
Memory limit: 1GB.
At least one of the digits of N is a 4.

Sample
Input Output
3
4 Case #1: 2 2
940 Case #2: 852 88
4444 Case #3: 667 3777
 [Link] 

On the Code Jam team, we enjoy sending each other pangrams, which are phrases that use each
letter of the English alphabet at least once. One common example of a pangram is "the quick
brown fox jumps over the lazy dog". Sometimes our pangrams contain confidential information —
for example, CJ QUIZ: KNOW BEVY OF DP FLUX ALGORITHMS — so we need to keep them secure.

We looked through a cryptography textbook for a few minutes, and we learned that it is very hard
to factor products of two large prime numbers, so we devised an encryption scheme based on that
fact. First, we made some preparations:

 We chose 26 different prime numbers, none of which is larger than some integer  N.
 We sorted those primes in increasing order. Then, we assigned the smallest prime to the
letter A, the second smallest prime to the letter B, and so on.
 Everyone on the team memorized this list.

Now, whenever we want to send a pangram as a message, we first remove all spacing to form a
plaintext message. Then we write down the product of the prime for the first letter of the
plaintext and the prime for the second letter of the plaintext. Then we write down the product of
the primes for the second and third plaintext letters, and so on, ending with the product of the
primes for the next-to-last and last plaintext letters. This new list of values is our ciphertext. The
number of values is one smaller than the number of characters in the plaintext message.

For example, suppose that N = 103 and we chose to use the first 26 odd prime numbers, because
we worry that it is too easy to factor even numbers. Then A = 3, B = 5, C = 7, D = 11, and so on, up
to Z = 103. Also suppose that we want to encrypt the CJ QUIZ... pangram above, so our plaintext
is CJQUIZKNOWBEVYOFDPFLUXALGORITHMS. Then the first value in our ciphertext is 7 (the prime
for C) times 31 (the prime for J) = 217; the next value is 1891, and so on, ending with 3053.

We will give you a ciphertext message and the value of N that we used. We will not tell you which
primes we used, or how to decrypt the ciphertext. Do you think you can recover the plaintext
anyway?

Input

The first line of the input gives the number of test cases, T. T test cases follow; each test case
consists of two lines. The first line contains two integers: N, as described above, and L, the length
of the list of values in the ciphertext. The second line contains L integers: the list of values in the
ciphertext.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting
from 1) and y is a string of L + 1 uppercase English alphabet letters: the plaintext.