Challenge 13 - R’lyeh

Last week, during our volcanic studies near Point Nemo, our radar system detected some anomalies in a previously unexplored area of the seabed. According to the data an unbelievably massive object, around 200 meters tall and 60 meters wide, was lying in an otherwise empty part of the ocean floor. We were ecstatic at first; no one was expecting a discovery of this magnitude and so we rushed to identify the object, sending our ROV to take some pictures of it.

When the first images finally arrived, we were puzzled. Although the ROV hadn't yet reached the object, it was close enough to shed some light on it, outlining its majestic contour. It seemed to be some kind of anthropomorphic statue, with a wide torso and what seemed like giant octopi tendrils coming out of its mouth. An ominous feeling set in my stomach but we would be foolish not to take this further: this was something unheard of and had implications that would change humanity forever. Or so we thought.

The statue was so big that it was impossible to take a clear look at it with our equipment. We needed a strong light to be able to discern details in those dark waters, so the ROV had to get close enough to it that we could never get a proper image of the complete sculpture. It seemed to be made out of a porous, black rock, probably some kind of tholeiitic basalt, and its surface was covered with deep inscriptions that lacerated the rock so deeply that they appeared to be pitch-black. They were numbers, we realized. Hundreds, thousands, millions of numbers crawling over the surface of this idol for who knows how many eons.

We needed to know what they meant. Something unearthly was driving us to uncover this mystery and made us study the statue for five long, sleepless days. Of the unspeakable horrors that we saw I shall tell you only what is strictly necessary in this letter. I shall not speak of the dark and cosmic horrors awaiting in the black depths, nor of the madness that took over our minds. We found out that some numbers were carved deep inside the rock itself while others were merely painted on its surface, as if written by some gigantic and otherworldy being. They were grouped subtly in pairs, made up of one carved and one written number. All except a few of them, which seemed to lie by themselves on the stone.

The lone numbers were missing their partners, we knew as much, although now my mind refuses to remember of how we came upon that knowledge. After a long strenuous effort, we made a breakthrough: the written number is always derived from the carved one, by a series of confusing mathematical operations. By reapplying this algorithm, we were able to reconstruct all of the pairs that were missing a written number. As hard as we tried, however, we were not able to reverse the process and obtain the missing carved numbers. We could not even be sure if every written number has a corresponding partner, but I suspect not all of them do; chaos should be expected when dealing with the offspring of Azathoth.

I am now the only one left and I am afraid that the same dementia that devoured my companions is taking hold of me. Before I fall, though, I will write down the algorithm that we found and all of the written numbers missing their carved partner. There is not much time left, so I must hurry. Please, whoever you are, if you have this letter in your hands you must finish our job before he wakes up. Ph'nglui mglw'nafh C'thulhu R'lyeh wgah'nagl fhtagn.

int64_t carvedToWritten(int64_t n)
{
    int64_t r = 0;
    for (int64_t i = 0; i < 64; ++i)
    {
        int64_t a = 0;
        for (int64_t j = n; j >= 0; --j)
        {
            int64_t b = 0;
            for (int64_t k = 0; k <= i; ++k)
            {
                int64_t c = a ^ ((i & (n ^ j) & 1) << k);
                a ^= (j & (1LL << k)) ^ b;
                b = (((c & j) | ((c ^ j) & b)) & (1LL << k)) << 1;
            }
        }
        r |= (a & (1LL << i));
    }
    return r;
}

Input

The first line will contain an integer C, the number of cases for our problem.
Each case consists of a line with an integer N, a written number.

Output

For each case, a line starting with "Case #x: " followed by the corresponding carved number. If there is more than one possible carved number, pick the smallest one. If the written number doesn't have a corresponding carved number, write "IMPOSSIBLE".

Examples

Case 1:
6

Case 2:
11

Case 3:
23

Case 4:
70787

Case 5:
163

In Case 1, the answer is 3. Notice that if you apply the nefarious function to 3 you obtain 6.
In Case 2, the answer is IMPOSSIBLE. There isn't a corresponding carved number for 11.
In Case 3, the answer is 6. Note that 23 could also be derived from 37, but 6 is smaller.
In Case 4, the answer is 398.
In Case 5, the answer is 8526.

Limits

• 1 ≤ Carved numbers ≤ 2³² - 1
• 1 ≤ Written numbers ≤ 2⁶⁴ - 1

Sample Input

5
6
11
23
70787
163

Sample Output

Case #1: 3
Case #2: IMPOSSIBLE
Case #3: 6
Case #4: 398
Case #5: 8526