Description

在本题中，你需要找出数字 $(3 + \sqrt{5})^n$ 小数点前的最后三位数字。

例如，当 $n = 5$ 时，$(3 + \sqrt{5})^5 = 3935.73982\dots$，答案是 $935$。

当 $n = 2$ 时，$(3 + \sqrt{5})^2 = 27.4164079\dots$，答案是 $027$。

Input Format

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

Output Format

对于每个输入用例，输出格式如下：

Case #$X$: $Y$

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

2
5
2

Case #1: 935
Case #2: 027

Hint

数据范围

• $1 \leq T \leq 100$

小数据集（15 分，测试点 1 - 可见）

• $2 \leq n \leq 30$

大数据集（35 分，测试点 2 - 隐藏）

• $2 \leq n \leq 2\times10^{10}$

由 ChatGPT 4.1 翻译