QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Total points: 50

# 5756. Numbers

统计

Problem

In this problem, you have to find the last three digits before the decimal point for the number (3 + √5)n.

For example, when n = 5, (3 + √5)5 = 3935.73982... The answer is 935.

For n = 2, (3 + √5)2 = 27.4164079... The answer is 027.

Input

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.

Output

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 + √5)n. In case that number has fewer than three integer digits, add leading zeros so that your output contains exactly three digits.

Limits

Time limit: 30 2 seconds per test set.

Memory limit: 1GB.

1 < T < 100

Small dataset (Test set 1 - Visible; 15 Points)

2 < n < 30

Large dataset (Test set 2 - Hidden; 35 Points)

2 < n < 2000000000

Sample

2
5
2
Case #1: 935
Case #2: 027