#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < int(n); i++)
using ll = long long;
using P = pair<int, int>;

template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }


int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int n, m; cin >> n >> m;
    vector<int> a(m), b(m);
    vector<char> c(m);
    rep(i, m) {
        cin >> a[i] >> b[i] >> c[i];
        a[i]--, b[i]--;
    }
    vector<vector<int>> g(n * n);
    auto to_one = [&](int x, int y) {
        return x * n + y;
    };
    auto to_two = [&](int x) {
        P res = {x / n, x % n};
        return res;
    };
    rep(i, m) {
        rep(j, m) {
            if(c[i] != c[j]) continue;
            g[to_one(a[i], a[j])].push_back(to_one(b[i], b[j]));
            g[to_one(a[i], b[j])].push_back(to_one(b[i], a[j]));
            g[to_one(b[i], a[j])].push_back(to_one(a[i], b[j]));
            g[to_one(b[i], b[j])].push_back(to_one(a[i], a[j]));
        }
    }
    const int INF = 1e9;
    vector<int> dist(n * n, INF);
    queue<int> que;
    rep(i, n) {
        que.push(to_one(i, i));
        dist[to_one(i, i)] = 0;
    }
    rep(i, m) {
        que.push(to_one(a[i], b[i]));
        chmin(dist[to_one(a[i], b[i])], 1);
        que.push(to_one(b[i], a[i]));
        chmin(dist[to_one(b[i], a[i])], 1);
    }
    while(!que.empty()) {
        int now = que.front();
        que.pop();
        for (auto nv : g[now]) {
            int cost = dist[now] + 2;
            if(dist[nv] != INF) continue;
            dist[nv] = cost;
            que.push(nv);
        }
    }
    int ans = min(dist[to_one(0, n - 1)], dist[to_one(n - 1, 0)]);
    cout << (ans == INF ? -1 : ans) << endl;
    return 0;
}

#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(),_obj.end()
#define F first
#define S second
#define pll pair<ll, ll> 
#define vll vector<ll>
ll n,m,a,b,c,k,temp,x,y,INF=1e18,s;
const int N=1e5+11,mod=1e9+7;
ll max(ll a,ll b) {return ((a>b)?a:b);}
ll min(ll a,ll b) {return ((a>b)?b:a);}
vll read(int n) {vll v(n);for (int i = 0; i < v.size(); i++)cin>>v[i];return v;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll gcd(ll a, ll b, ll& x, ll& y) 
{
    //ax+by=gcd;
    //modular inverse =take gcd with m then (x%m+m)%m;
    if (b == 0) 
    {
        x = 1;
        y = 0;
        return a;
    }
    ll x1, y1;
    ll d = gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}
void sol(void)
{
cin>>n>>s>>k;
ll rem=n-s;
ll g1=gcd(n,rem,x,y);
ll g2=gcd(g1,k,x,y);
k/=g2;
n/=g2;
rem/=g2;
if(gcd(k,n,x,y)!=1)
cout<<-1<<'\n';
else
cout<<(((x%n+n)%n)*rem)%n<<'\n';
return ;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int test=1;
    cin>>test;
    while(test--) sol();
}
