#include<cstdio>
#include<iostream>
#include<string>
#include<cstdlib>
#include<queue>
#include<stack>
#include<utility>
#include<string>
#include<cstring>
#include<set>
#include<cmath>
#include<vector>
#include<fstream>
#include<map>
#include<list>
#include<algorithm>
#define VI vector<int>
#define VF vector<float>
#define VD vector<double>
#define VC vector<char>
#define VVI vector<VI>
#define VVF vector<VF>
#define VVD vector<VD>
#define VVC vector<VC>
#define SI set<int>
#define SF set<float>
#define SD set<double>
#define SC set<char>
#define SSI set<SI>
#define SSF set<SF>
#define SSD set<SD>
#define SSC set<SC>
#define STI stack<int>
#define STF stack<float>
#define STD stack<double>
#define STC stack<char>
#define STSTI stack<STI>
#define STSTF stack<STF>
#define STSTD stack<STD>
#define STSTC stack<STC>
#define MOD 314159
typedef long long int LLD;
typedef unsigned long long int LLU;
using namespace std;
int even[1000001], odd[1000001];
int main(){
odd[1] = 1;
even[1] = 9;
for(int i=2;i<1000001;i++){
odd[i] = (((9 * odd[i-1]) % MOD) + even[i-1]) % MOD;
even[i] = (((9 * even[i-1]) % MOD) + odd[i-1]) % MOD;
}
int t, n;
scanf("%d", &t);
while(t--){
scanf("%d", &n);
printf("%d\n", even[n]);
}
return 0;
}
CiNpbmNsdWRlPGNzdGRpbz4KI2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPHN0cmluZz4KI2luY2x1ZGU8Y3N0ZGxpYj4KI2luY2x1ZGU8cXVldWU+CiNpbmNsdWRlPHN0YWNrPgojaW5jbHVkZTx1dGlsaXR5PgojaW5jbHVkZTxzdHJpbmc+CiNpbmNsdWRlPGNzdHJpbmc+CiNpbmNsdWRlPHNldD4KI2luY2x1ZGU8Y21hdGg+CiNpbmNsdWRlPHZlY3Rvcj4KI2luY2x1ZGU8ZnN0cmVhbT4KI2luY2x1ZGU8bWFwPgojaW5jbHVkZTxsaXN0PgojaW5jbHVkZTxhbGdvcml0aG0+CiNkZWZpbmUgVkkgdmVjdG9yPGludD4KI2RlZmluZSBWRiB2ZWN0b3I8ZmxvYXQ+CiNkZWZpbmUgVkQgdmVjdG9yPGRvdWJsZT4KI2RlZmluZSBWQyB2ZWN0b3I8Y2hhcj4KI2RlZmluZSBWVkkgdmVjdG9yPFZJPgojZGVmaW5lIFZWRiB2ZWN0b3I8VkY+CiNkZWZpbmUgVlZEIHZlY3RvcjxWRD4KI2RlZmluZSBWVkMgdmVjdG9yPFZDPgojZGVmaW5lIFNJIHNldDxpbnQ+CiNkZWZpbmUgU0Ygc2V0PGZsb2F0PgojZGVmaW5lIFNEIHNldDxkb3VibGU+CiNkZWZpbmUgU0Mgc2V0PGNoYXI+CiNkZWZpbmUgU1NJIHNldDxTST4KI2RlZmluZSBTU0Ygc2V0PFNGPgojZGVmaW5lIFNTRCBzZXQ8U0Q+CiNkZWZpbmUgU1NDIHNldDxTQz4KI2RlZmluZSBTVEkgc3RhY2s8aW50PgojZGVmaW5lIFNURiBzdGFjazxmbG9hdD4KI2RlZmluZSBTVEQgc3RhY2s8ZG91YmxlPgojZGVmaW5lIFNUQyBzdGFjazxjaGFyPgojZGVmaW5lIFNUU1RJIHN0YWNrPFNUST4KI2RlZmluZSBTVFNURiBzdGFjazxTVEY+CiNkZWZpbmUgU1RTVEQgc3RhY2s8U1REPgojZGVmaW5lIFNUU1RDIHN0YWNrPFNUQz4KI2RlZmluZSBNT0QgMzE0MTU5CnR5cGVkZWYgbG9uZyBsb25nIGludCBMTEQ7CnR5cGVkZWYgdW5zaWduZWQgbG9uZyBsb25nIGludCBMTFU7CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmludCBldmVuWzEwMDAwMDFdLCBvZGRbMTAwMDAwMV07CmludCBtYWluKCl7Cm9kZFsxXSA9IDE7CmV2ZW5bMV0gPSA5Owpmb3IoaW50IGk9MjtpPDEwMDAwMDE7aSsrKXsKb2RkW2ldID0gKCgoOSAqIG9kZFtpLTFdKSAlIE1PRCkgKyBldmVuW2ktMV0pICUgTU9EOwpldmVuW2ldID0gKCgoOSAqIGV2ZW5baS0xXSkgJSBNT0QpICsgb2RkW2ktMV0pICUgTU9EOwp9CmludCB0LCBuOwpzY2FuZigiJWQiLCAmdCk7CndoaWxlKHQtLSl7CnNjYW5mKCIlZCIsICZuKTsKcHJpbnRmKCIlZFxuIiwgZXZlbltuXSk7Cn0KcmV0dXJuIDA7Cn0=