Bạn có vô hạn những viên gạch có hình chữ nhật \(2 \times 1\) và những viện gạch có hình vuông \(2 \times 2\) bị khuất phần tư một góc. Hãy đếm số cách lát những viên gạch này thành một hình chữ nhật \(2 \times N\).

Input

• Gồm nhiều test, dòng đầu ghi số lượng test \(T ( T\le 100 )\).
• \(T\) dòng sau mỗi dòng ghi một số dương \(N(N\leq 10^9)\).

Output

• Ghi ra \(T\) dòng, mỗi dòng chứa số thứ tự của test và số cách lát tương ứng lấy phần dư cho 10007.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N \leq 100\)
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm

Example

2
3
10

Case 1: 5
Case 2: 1255