package main

import (
	"bufio"
	"fmt"
	"os"
)

func matMul(a, b []int) []int {
	c := make([]int, 4)
	c[0] = (a[0]*b[0] + a[1]*b[2]) % 1000
	c[1] = (a[0]*b[1] + a[1]*b[3]) % 1000
	c[2] = (a[2]*b[0] + a[3]*b[2]) % 1000
	c[3] = (a[2]*b[1] + a[3]*b[3]) % 1000
	return c
}

func estimate(scanner *bufio.Scanner) []string {
	caseCnt := ReadInt(scanner)
	answer := make([]string, caseCnt)
	// Conjugation is the most important clue. Assume that a = 3 + √5,
	// b = 3 - √5, then Xn = a^n + b^n is an integer. What's more, b^n < 1,
	// so Xn is the 1st number that larger than a^n.
	// a + b = 6, ab = 4, so a^2 - 6 + 4 = 0, b^2 - 6 + 4 = 0,
	// X(n+2) = 6X(n+1) - 4Xn, for | X(n+1) | _   | X(n)   |
	//                             | X(n)   | - B | X(n-1) |,
	// B is [[6, -4], [1, 0]], B^n [X(1), X(0)] = [X(n+1), X(n)]
	for i := 0; i < caseCnt; i++ {
		power := ReadInt(scanner)
		base := []int{6, -4, 1, 0}
		res := []int{1, 0, 0, 1} // E
		for power != 0 {
			if power&1 == 1 {
				res = matMul(res, base)
			}
			base = matMul(base, base)
			power /= 2
		}
		// X1 = 6, X0 = 2
		product := (6*res[2] + 2*res[3]) % 1000
		product = (product + 999) % 1000 // a^n = Xn - 1
		answer[i] = fmt.Sprintf("%03d", int(product))
	}
	return answer
}

func main() {
	inputFiles := []string{"C-small-practice.in", "C-large-practice.in", "test.in"}
	outputFiles := []string{"result-small.out", "result-large.out", "test.out"}
	const (
		small = iota
		large
		test
	)

	fileType := test

	fin, _ := os.Open(inputFiles[fileType])
	defer fin.Close()

	scanner := bufio.NewScanner(fin)
	answer := estimate(scanner)

	fout, _ := os.Create(outputFiles[fileType])
	defer fout.Close()

	for i, v := range answer {
		s := fmt.Sprintf("Case #%d: %s\n", i+1, v)
		fout.WriteString(s)
	}
}