github.com/captn3m0/codechef.git

---
{"languages_supported":{"0":"NA"},"title":"STEPNUMS","category":"NA","old_version":true,"problem_code":"STEPNUMS","tags":{"0":"NA"},"layout":"problem"}
---

<h3> All submissions for this problem are available. </h3><p>Call a number stepping if adjacent digits, as well as the first and last digits, differ by one. How many n-digit base 11 stepping numbers are there? Give your answer modulo 4294967143.</p>
<p>For example, 8789A9 is a 6-digit base 11 stepping number. 9A0A and 234 are not stepping.</p>
<h3>Input</h3>
<p>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 &lt;= n &lt; 2<sup>64</sup>).</p>
<h3>Output</h3>
<p>Output the answer to each test case on a separate line.</p>
<h3>Example</h3>
<pre><b>Input:</b>
4
2
4
6
10

<b>Output:</b>
19
54
171
1958
</pre>
<p></p>