BYTESH1  Filchs Dilemna
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:
20171028 05:29:05
Good problem ! Don't forget to mod the ans while generating. 

Piyush Kumar:
20160609 20:54:56
No extreme test cases! 

trieuman189:
20151027 19:59:48
Blog Thuật toán SPOJ can help you : http://www.oni.vn/uR57W 

Deepak Singh Tomar:
20150705 15:24:44
my 150th... :) 

Mitch Schwartz:
20140404 17:14:54
Images restored. 

Rishav Goyal:
20140318 17:16:27
nice one !! love such kinda problems 

Paul Draper:
20121119 11:17:43
I've made a copy of the problem description (as of 20121119) with images here. Last edit: 20121119 11:18:11 

Crazzyy:
20120203 17:33:07
image not visible 

islam:
20100727 09:47:05
N is not precise , N<100000 

David Gómez:
20091227 05:17:52
Images are not visible 
Added by:  Paritosh Aggarwal 
Date:  20090221 
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 PASGPC PASFPC PERL PHP PIKE PRLGswi PYTHON RUBY SCM qobi SCM guile ST TEXT WHITESPACE 