#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <climits>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <bits/stdc++.h>
using namespace std;

#define lson 2*i  
#define rson 2*i+1  
#define LS l,mid,lson  
#define RS mid+1,r,rson  
#define UP(i,x,y) for(i=x;i<=y;i++)  
#define DOWN(i,x,y) for(i=x;i>=y;i--)  
#define MEM(a,x) memset(a,x,sizeof(a))  
#define W(a) while(a)  
#define gcd(a,b) __gcd(a,b)  
#define ll long long  
#define MAX 1000005  
#define MOD 1000000007  
#define EXP 1e-8  
#define lowbit(x) (x&-x)  
// const int INF = 0x1fffffffffffffff;
const int INF = INT_MAX;
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
void chmin(ll& a, ll b){ if(a > b) a = b; }
void chmax(ll& a, ll b){ if(a < b) a = b; }

int main () {
    int n, m; cin >> n >> m;
    int x, y, z;
    vector<vector<pair<int, int>>> cs(n+1);
    for (int i = 0; i < m; ++i){
        cin >> x >> y >> z;
        cs[x-1].emplace_back(y, z);
    }
    vector<ll> dp(1 << n);
    dp[0] = 1;
    queue<int> q;
    unordered_set<int> hash; 
    q.push(0);
    int pos = 0;
    while (!q.empty()) {
        int size = q.size(); 
        while (size--) {
            int state = q.front(); q.pop();
            for (int i = 0; i < n; ++i) {
                int num = (1 << i);
                if (state & num) continue;
                int newState = state | num;
                bool flag = true;
                for (auto &it : cs[pos]) {
                    y = it.first, z = it.second;
                    int mask = (1 << y) - 1;
                    if (__builtin_popcount(newState & mask) > z) {
                        flag = false; break;
                    }
                }
                if (flag) dp[newState] += dp[state];
                // cout << state << ' ' << newState << ' ' << dp[newState] << endl;
                if (!hash.count(newState))
                    q.push(newState), hash.insert(newState);
            }
        }
        // cout << pos <<endl;
        pos++;
    }
    cout << dp[(1<<n)-1] << endl;
    return 0;
}
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define cool ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int  long long int
#define pb push_back
#define fe first
#define lb lower_bound 
#define ub upper_bound
#define pii pair<pair<int,int>,pair<int,int> >
#define se second
#define endl "\n"
#define pi pair<int, int>
#define mi          map<int,int>
#define mii         map<pi,int>
#define vi vector<int> 
#define vvi vector<vi>
#define bs   binary_search
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rep1(i,a,b) for(int i=a;i<=b;i++)	
#define all(c) (c).begin(),(c).end()
#define sz(x)       (int)x.size() 
#define PI 3.14159265358979323846
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> o_set;
 
 
 const int N=3e5+10;
 
 const int INF=1e18;
 
 int mod= 1e9+7;
 int dx[4]={0,0,+1,-1};
 int dy[4]={+1,-1,0,0};  
 
 
int po(int a, int b) {
	int res = 1;
	while (b > 0) {
		if (b & 1)
			res = (res%mod * a%mod) % mod;
		a =(a%mod*a%mod) % mod;
		b >>= 1;
	}
	 return res;
  }
 

int gcdExtended(int a,int b,int* x,int* y) {
	 if(a==0) {
			  *x=0,*y=1;
			  return  b;
			}
		int x1,y1;
		int g=gcdExtended(b%a,a,&x1,&y1);
		*x=y1-(b/a)*x1;
		*y=x1;
		return g;
}



int modInverse(int a,int m) {
	  int x,y;
	  int g=gcdExtended(a,m,&x,&y);
	  int res=(x%m+m)%m;
	  return res;
	} 
 
void solve() {		 
	int n,s,k;
	cin>>n>>s>>k;
	int g=__gcd(n,k);
	int lt=n-s;
	if((lt%g)!=0) {
		   cout<<-1<<endl;
		   return;
		}
		n/=g;
		k/=g;
		lt/=g;
		int yo=modInverse(k,n);
	 int ans=((lt)*yo)%n; 
	 cout<<ans<<endl;  	
}
 
 
	
int32_t main() {
	cool;
	int t=1;
	//~ freopen("input.txt","r",stdin);
	//~ freopen("output.txt","w",stdout);	
	
	cin>>t;
	while(t--)
	  solve();
 
  return 0;	   
}






























