SP14991 EGCJPURE - Your Rank is Pure (EXTREME ver)

Note: The problem description is same as [GCJPURE](../GCJPURE/ "GCJPURE"), but with more higher constraints (to become more challenging), more strict time limit (to reject bad complexity), and more strict source limit (to reject hardcoded precomputation). Good Luck. ### Problem Description Pontius: You know, I like this number 127, I don't know why.

The first line of the input gives the number of test cases, **T**. **T** lines follow. Each contains a single integer **n**.

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the answer as described above.