题目描述

In this problem, you have to find the last three digits before the decimal point for the number $(3 + \sqrt{5})^n$.

For example, when $n = 5$, $(3 + \sqrt{5})^5 = 3935.73982\dots$ The answer is $935$.

For $n = 2$, $(3 + \sqrt{5})^2 = 27.4164079\dots$ The answer is $027$.

输入格式

The first line of input gives the number of cases, $T$. $T$ test cases follow, each on a separate line. Each test case contains one positive integer $n$.

输出格式

For each input case, you should output:

Case #$X$: $Y$

where $X$ is the number of the test case and $Y$ is the last three integer digits of the number $(3 + \sqrt{5})^n$. In case that number has fewer than three integer digits, add leading zeros so that your output contains exactly three digits.

2
5
2

Case #1: 935
Case #2: 027

提示

Limits

• $1 \leq T \leq 100$

Small dataset (15 Pts, Test set 1 - Visible)

• $2 \leq n \leq 30$

Large dataset (35 Pts, Test set 2 - Hidden)

• $2 \leq n \leq 20000000000$