Stepping Number

All submissions for this problem are available.
Call a number stepping if adjacent digits, as well as the first and last digits, differ by one. How many ndigit base 11 stepping numbers are there? Give your answer modulo 4294967143.
For example, 8789A9 is a 6digit base 11 stepping number. 9A0A and 234 are not stepping.
INPUT
The first line contains an integer T, the number of test cases (about 20000). Each of the next T lines contains an integer n (2 <= n < 264).
Output
Output the answer to each test case on a separate line.
Example
Input
4 2 4 6 10 etc.Output
19 54 171 1958 etc.
Author:  prakhargahlot 
Tags  prakhargahlot 
Date Added:  11112010 
Time Limit:  0.1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, COB, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, kotlin, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, rust, SCALA, SCM chicken, SCM guile, SCM qobi, ST, swift, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 