[HomeTrainingProblemsContestsC Language]  [LoginRegister] 
Problems Status Rank 
Problem 1231
Especial 01 String
Time Limit: 1000ms
Memory Limit: 65536kb Description
Assuming there is a 01 string with its length L,what’s more,a legal 01 string can’t contain any substring as follows: '101', '10011'.For example, '10001' is a legal string,because it doesn’t contain any substring '101' or '10011'。But '100000101' is an illegal string,because it contains substring '101' Can you compute the numbers of such legal string with its length L? Maybe the result will be very huge,so divide by 20110514,then output the remaider. Input
Input a number T in the first line,representing T test cases below. Then each case only contains a number L (3<=L<=1000000000).
Output
Output the correct answer.
Sample Input
2 3 5 Sample Output
7 20 Hint
when L=3,Legal strings are as follows: 000,001,010,011,100,110,111.
