#include<iostream>
#define mod 314159
using namespace std;
long long moduluss(long long base, long long exponent)
{
long long result = 1;
while (exponent > 0)
{
if (exponent % 2 == 1)
result = (result * base) % mod;
exponent = exponent >> 1;
base = (base * base) % mod;
}
return result;
}
int main()
{int t;
int i;
long long n;
cin>>t;
while(t--)
{
cin>>n;
cout<<((moduluss(10,n)+moduluss(8,n))%mod)/2<<endl;}
//else
return 0;}
I2luY2x1ZGU8aW9zdHJlYW0+CgojZGVmaW5lIG1vZCAzMTQxNTkKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKbG9uZyBsb25nIG1vZHVsdXNzKGxvbmcgbG9uZyBiYXNlLCBsb25nIGxvbmcgZXhwb25lbnQpCnsKICAgIGxvbmcgbG9uZyByZXN1bHQgPSAxOwogICAgd2hpbGUgKGV4cG9uZW50ID4gMCkKICAgIHsKICAgICAgICBpZiAoZXhwb25lbnQgJSAyID09IDEpCiAgICAgICAgICAgIHJlc3VsdCA9IChyZXN1bHQgKiBiYXNlKSAlIG1vZDsKICAgICAgICBleHBvbmVudCA9IGV4cG9uZW50ID4+IDE7CiAgICAgICAgYmFzZSA9IChiYXNlICogYmFzZSkgJSBtb2Q7CiAgICB9CiAgICByZXR1cm4gcmVzdWx0Owp9CiAKaW50IG1haW4oKQogCntpbnQgdDsKaW50IGk7CmxvbmcgbG9uZyBuOwpjaW4+PnQ7CndoaWxlKHQtLSkKewoJY2luPj5uOwogCmNvdXQ8PCgobW9kdWx1c3MoMTAsbikrbW9kdWx1c3MoOCxuKSklbW9kKS8yPDxlbmRsO30KLy9lbHNlCnJldHVybiAwO30=