#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;

#define FOR(i,a) for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); ++ i)

int MOD;

void add(int &a, int b)
{
//    fprintf(stderr, "a = %d, b = %d, MOD = %d\n", a, b, MOD);
    assert(0 <= b && b < MOD);
    a += b;
    if (a >= MOD) {
        a -= MOD;
    }
}

const int MAXW = 7;
const int MAXH = 100;
const int MAXMOD = 1000000007;

int main()
{
    //freopen("F.in", "r", stdin);

    int T;
    for (assert(scanf("%d", &T) == 1 && 1 <= T && T <= 10); T --;) {
        int w, h;
        assert(scanf("%d%d%d", &w, &h, &MOD) == 3);
        assert(1 <= w && w <= MAXW);
        assert(1 <= h && h <= MAXH);
        assert(1 <= MOD && MOD <= MAXMOD);

        int pw4[w + 1];
        pw4[0] = 1;
        for (int i = 1; i <= w; ++ i) {
            pw4[i] = pw4[i - 1] * 4;
        }

        int initial = pw4[w - 1] * 3;
        int f[2][pw4[w]];
        memset(f, 0, sizeof(f));
        int now = 0, old = 1;
        f[now][initial] = 1 % MOD;
        for (int i = 0; i < h; ++ i) {
            for (int j = (i == 0 ? 1 : 0); j < w; ++ j) {
                now = 1 - now;
                old = 1 - old;
                memset(f[now], 0, sizeof(f[now]));
                for (int mask = 0; mask < pw4[w]; ++ mask) {
                    if (f[old][mask]) {
                        int left = mask / pw4[w - 1];
                        int upper = mask % 4;

                        // as a rock
                        if (true) {
                            int new_mask = mask / 4;
                            add(f[now][new_mask], f[old][mask]);
                        }

                        // as an empty
                        if (true) {
                            int current = upper >= 2 ? 3 : 1;
                            int new_mask = mask / 4;
                            if (j - 1 >= 0) {
                                current = max(left == 3 ? 2 : 1, current);
                                if (current == 3) {
                                    if (left == 1) {
                                        new_mask += pw4[w - 2];
                                    }
                                }
                            }
                            new_mask += current * pw4[w - 1];
                            add(f[now][new_mask], f[old][mask]);
                        }
                    }
                }
            }
        }
        int answer = 0;
        for (int mask = 0; mask < pw4[w]; ++ mask) {
            bool valid = false;
            for (int i = 0; i < w; ++ i) {
                if (mask / pw4[i] % 4 >= 2) {
                    valid = true;
                    break;
                }
            }
            if (valid) {
                add(answer, f[now][mask]);
            }
        }
        printf("%d\n", answer);
    }
    return 0;
}