BYTESH1 - Filchs Dilemna

no tags 

Filch’s Dilemma (15 points) Argus Filch, the caretaker of Hogwarts, has been given the task to carpet the way to Hogwarts through the grounds. The way is 2 units wide and ‘N’ units long. He has only two types of carpets available, one is 1 unit wide and 2 units long and the other one is L shaped, having 3 square units. Here are their pictures:

Filch can rotate the carpets when he lays them and has an infinite supply of both types of carpets. As Filch is a squib he cannot magically arrange the carpets and has to resort to logic to find out all possible ways of carpeting the way. He wishes to calculate the number of different ways of carpeting the way.
For instance, a 2x3 way can be carpeted in 5 different ways as follows:


Notice that both types of carpets can be used simultaneously. Consider, for instance the following way of carpeting a 2x4 way:


Given N, you have to help Filch determine the number of ways to carpet the way of size 2xN. Since this number may be very large, it is sufficient to report the last four digits of the answer. For instance the number of ways to carpet a 2x13 way is 13465. Your program should just print 3465. If the answer is in 4 digits or less it should print the entire answer. For example, if N=3 you should print 5.

Input

The first line of the input consists of a single integer T(1<=T<=100). Each of the next T lines consists of a single integer N (1<=N<=1000000), indicating the size of the way.

Output

For each test case, output the last four digits of the number of ways of carpeting the 2xN way. If the answer involves fewer than 4 digits, print the entire number.
Important Update - If the output of last four digits has leading zeros, print the output without the leading zeros

Example

Input:
2
3
13

Output:
5
3465

hide comments
trijeet: 2017-10-28 05:29:05

Good problem ! Don't forget to mod the ans while generating.

Piyush Kumar: 2016-06-09 20:54:56

No extreme test cases!

trieuman189: 2015-10-27 19:59:48

Blog Thuật toán SPOJ can help you : http://www.oni.vn/uR57W

Deepak Singh Tomar: 2015-07-05 15:24:44

my 150th... :)

Mitch Schwartz: 2014-04-04 17:14:54

Images restored.

Rishav Goyal: 2014-03-18 17:16:27

nice one !! love such kinda problems

Paul Draper: 2012-11-19 11:17:43

I've made a copy of the problem description (as of 2012-11-19) with images here.

Last edit: 2012-11-19 11:18:11
Crazzyy: 2012-02-03 17:33:07

image not visible

islam: 2010-07-27 09:47:05

N is not precise , N<100000

David Gómez: 2009-12-27 05:17:52

Images are not visible


Added by:Paritosh Aggarwal
Date:2009-02-21
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM qobi SCM guile ST TEXT WHITESPACE