#include <cstdio>
using namespace std;
int T, n, m, i, j, dp[2][5005][5005], ans = 0, mod;
int M(int x) {
    if (x < 0)
        return x + mod;
    if (x >= mod)
        return x - mod;
    return x;
}
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &n, &m, &mod);
        m--;
        for (i = 1; i < n; i++) dp[0][0][i] = 1;
        dp[1][0][0] = 1;
        for (i = 1; i <= m; i++) {
            for (j = 1; j < n; j++) {
                dp[0][i][j] = (dp[0][i - 1][j - 1] + 2LL * dp[0][i - 1][j] + dp[0][i - 1][j + 1]) % mod;
                dp[1][i][j] = (dp[1][i - 1][j - 1] + 2LL * dp[1][i - 1][j] + dp[1][i - 1][j + 1]) % mod;
            }
            dp[1][i][0] = (2LL * dp[1][i - 1][0] + dp[1][i - 1][1] + dp[0][i - 1][1]) % mod;
        }
        for (i = 0; i < n; i++) ans = M(ans + dp[1][m][i]);
        ans = 4LL * ans % mod;
        printf("%d\n", ans);
        for (i = 0; i <= m + 1; i++)
            for (j = 0; j <= n + 1; j++) dp[0][i][j] = dp[1][i][j] = 0;
        ans = 0;
    }
    return 0;
}