#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const long long mod = ;

const long long mod2 = mod *  + ;

const long long mod3 = mod2 * ;

typedef long long ll;

int T, len, shu[];

char s[];

ll t;

struct node

{

    ll a[][];

    node(){ memset(a, , sizeof(a)); }

}x, y;

ll zhuanhuan()

{

    ll res = ;

    for (int i = ; i <= len; i++)

        shu[i] = s[i] - '';

    for (int i = ; i <= len; i++)

        res = (res *  + shu[i]) % mod3;

    return res;

}

node mul1(node x, node y)

{

    node p;

    memset(p.a, , sizeof(p.a));

    for (int i = ; i <= ; i++)

        for (int j = ; j <= ; j++)

            for (int k = ; k <= ; k++)

                p.a[i][j] = (p.a[i][j] + x.a[i][k] * y.a[k][j] % mod2) % mod2;

    return p;

}

node mul2(node x, node y)

{

    node p;

    memset(p.a, , sizeof(p.a));

    for (int i = ; i <= ; i++)

        for (int j = ; j <= ; j++)

            for (int k = ; k <= ; k++)

                p.a[i][j] = (p.a[i][j] + x.a[i][k] * y.a[k][j] % mod) % mod;

    return p;

}

ll qpow1(ll b)

{

    x.a[][] = ;

    x.a[][] = ;

    y.a[][] = ;

    y.a[][] = y.a[][] = y.a[][] = ;

    while (b)

    {

        if (b & )

            x = mul1(x, y);

        y = mul1(y, y);

        b >>= ;

    }

    return x.a[][];

}

ll qpow2(ll b)

{

    x.a[][] = ;

    x.a[][] = ;

    y.a[][] = ;

    y.a[][] = y.a[][] = y.a[][] = ;

    while (b)

    {

        if (b & )

            x = mul2(x, y);

        y = mul2(y, y);

        b >>= ;

    }

    return x.a[][];

}

int main()

{

    scanf("%d", &T);

    while (T--)

    {

        scanf("%s", s + );

        len = strlen(s + );

        t = zhuanhuan();

        t = qpow1(t);

        printf("%lld\n", qpow2(t));

    }

    return ;

}