博客

#include<stdio.h>
#include<math.h>

int main () {
    int t;
    scanf("%d", &t);
    while(t--) {
        int a, count, m;
        scanf("%d", &a);
        if(a == 1) {
            printf("1\n");
            continue;
        }
        count = a / 3;
        m = a % 3;
        if(m == 1) {
            m = 4;
            count = count -1;
        }
        long long ans = 1;
        for(int i = 1; i <= count; i++) {
            ans *= 3;
            ans %= 2000000000000000003;
        }
        if(m != 0) {
            ans *= m;
        }
        printf("%lld\n", ans);
    }

    return 0;
}