SP14991 EGCJPURE - Your Rank is Pure (EXTREME ver)

请注意：本文描述的题目与 [GCJPURE](../GCJPURE/ "GCJPURE") 相同，但在以下方面有所不同：数据范围更大（以增加难度），时间限制更严格（以过滤掉高复杂度算法），以及代码长度限制更严格（以防硬编码预处理）。祝好运。 ### 说明 庞修斯说：“你知道吗？我喜欢数字 127，但我也说不清楚为什么。”

第一行输入一个整数 **T**，表示测试用例的数量。接下来的 **T** 行中，每行有一个整数 **n**。

对于每个测试用例，请输出一行，格式为 "Case #x: y"。其中，x 表示测试用例的编号（从 1 开始），y 是依据题目要求所计算出的答案。 **本翻译由 AI 自动生成**