#include <algorithm>

 #include<iostream>

 #include <cstdio>

 #include <vector>

 #include <cstring>

 using namespace std;

 typedef long long ll;

 const int maxn =  + ;

 const int mod = ;

 int n, m, ans;

 int dp[][maxn][maxn][maxn];

 vector <pair<int, int>> a[maxn];

 int main() {

     int pos;

     cin >> pos;

     while (pos--) {

         int ans = ;

         scanf("%d %d", &n, &m);

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

             a[i].clear();

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

             int l, r, x;

             scanf("%d%d%d", &l, &r, &x);

             a[r].push_back(pair<int, int>(l, x));

         }

         dp[][][][] = ;

         int now = ;

         for (int i = ; i <= n; i++, now ^= ) {

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

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

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

                         dp[now][j][k][t] = ;

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

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

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

                         dp[now][j][k][t] = (dp[now ^ ][j][k][t] + dp[now][j][k][t]) % mod;

                         dp[now][i - ][k][t] = (dp[now ^ ][j][k][t] + dp[now][i - ][k][t]) % mod;

                         dp[now][i - ][j][t] = (dp[now ^ ][j][k][t] + dp[now][i - ][j][t]) % mod;

                         dp[now][i - ][j][k] = (dp[now ^ ][j][k][t] + dp[now][i - ][j][k]) % mod;

                     }

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

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

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

                         for (auto tmp : a[i])

                             if ( + (j >= tmp.first) + (k >= tmp.first) + (t >= tmp.first) != tmp.second)

                                 dp[now][j][k][t] = ;

         }

         now = n & ;

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

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

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

                     ans = (ans + dp[now][i][j][k]) % mod;

         printf("%d\n", ans);

     }

 }