P13459 [GCJ 2008 #1A] Numbers

在本题中，你需要找出数字 $(3 + \sqrt{5})^n$ 小数点前的最后三位数字。 例如，当 $n = 5$ 时，$(3 + \sqrt{5})^5 = 3935.73982\dots$，答案是 $935$。 当 $n = 2$ 时，$(3 + \sqrt{5})^2 = 27.4164079\dots$，答案是 $027$。

输入的第一行包含一个整数 $T$，表示测试用例的数量。接下来的 $T$ 行，每行包含一个正整数 $n$，表示一个测试用例。

对于每个输入用例，输出格式如下： Case #$X$: $Y$ 其中 $X$ 表示测试用例编号，$Y$ 表示 $(3 + \sqrt{5})^n$ 小数点前的最后三位数字。如果该数字不足三位，需要在前面补零，使输出恰好为三位数字。

**数据范围** - $1 \leq T \leq 100$ **小数据集（15 分，测试点 1 - 可见）** - $2 \leq n \leq 30$ **大数据集（35 分，测试点 2 - 隐藏）** - $2 \leq n \leq 2\times10^{10}$ 由 ChatGPT 4.1 翻译