#include <iostream>
#include <vector>

using std::vector;

bool Bit(int mask, int pos) {
  return ((mask >> pos) & 1);
}

bool CheckOK(int mask1, int mask2, int m) {
  for (int i = 0; i < m - 1; ++i) {
    if (Bit(mask1, i) == Bit(mask2, i) &&
      Bit(mask1, i + 1) == Bit(mask2, i + 1) &&
      Bit(mask1, i) == Bit(mask1, i + 1)) {
      return false;
    }
  }
  return true;
}

vector<vector<int>> IsOK(int m) {
  vector<vector<int>> is_ok(1 << m);
  for (int left_mask = 0; left_mask < (1 << m); ++left_mask) {
    vector<int> temp_is_ok(1 << m);
    for (int right_mask = 0; right_mask < (1 << m); ++right_mask) {
      temp_is_ok[right_mask] = CheckOK(left_mask, right_mask, m);
    }
    is_ok[left_mask] = temp_is_ok;
  }
  return is_ok;
}

vector<vector<int>> MatrixMultiplication(vector<vector<int>> first_matrix,
                                         vector<vector<int>> second_matrix, int gor_size, int mod, int m) {
  int matrix_size = (1 << m);
  vector<vector<int>> res_matrix(matrix_size, vector<int>(gor_size, 0));
  for (int i = 0; i < matrix_size; ++i) {
    for (int j = 0; j < gor_size; ++j) {
      for (int k = 0; k < matrix_size; ++k) {
        res_matrix[i][j] += ((long long)(first_matrix[i][k]) * (long long)(second_matrix[k][j])) % mod;
        res_matrix[i][j] %= mod;
      }
    }
  }
  return res_matrix;
}

vector<vector<int>> MatrixDegree(long long n, vector<vector<int>>& matrix, int mod, int m) {
  int matrix_size = (1 << m);
  if (n == 1) {
    return matrix;
  }
  if (n % 2 == 0) {
    vector<vector<int>> temp_matrix = MatrixDegree(n / 2, matrix, mod, m);
    return MatrixMultiplication(temp_matrix, temp_matrix, matrix_size, mod, m);
  }
  return MatrixMultiplication(matrix, MatrixDegree(n - 1, matrix, mod, m), matrix_size, mod, m);
}

int main() {
  int T;
  std::cin >> T;
  while (T-- > 0) {
    int m, mod;
    long long n;
    std::cin >> n >> m >> mod;
    if (n == 1) {
      std::cout << (1 << m) % mod << "\n";
      continue;
    }
    vector<vector<int>> pretty_patterns_base((1 << m), vector<int>(1, 1));
    vector<vector<int>> is_ok = IsOK(m);
    vector<vector<int>>IsOKDegree = MatrixDegree(n - 1, is_ok, mod, m);
    vector<vector<int>> pretty_pattern = MatrixMultiplication(IsOKDegree, pretty_patterns_base, 1, mod, m);
    long long answer = 0;
    for (int i = 0; i < (1 << m); ++i) {
      answer += pretty_pattern[i][0];
      answer %= mod;
    }
    std::cout << answer << "\n";
  }
}