#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<vector<int>> vvi;
typedef vector<vector<long long>> vvl;

const int INF=1e8;
void chmin(int& x, int y){ x=min(x,y);}

int main(){
  int n;
  cin >> n;
  vi x(n),y(n),z(n);
  rep(i,n) cin >> x[i] >> y[i] >> z[i];
  int n2=1<<n;
  vvi dist(n,vi(n));
  rep(i,n) rep(j,n) dist[i][j]=abs(x[j]-x[i])+abs(y[j]-y[i])+max(0,z[j]-z[i]);
  vvi dp(n2,vi(n,INF));
  rep(i,n){
    if(i==0) continue;
    dp[1<<i][i]=dist[0][i];
  }
  rep(i,n2){
    rep(j,n){
      if(!(i>>j&1)) continue;
      rep(k,n){
        if(i>>k&1) continue;
        chmin(dp[i|1<<k][k],dp[i][j]+dist[j][k]);
      }
    }
  }
  cout << dp[n2-1][0];
  return 0;
}
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

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

#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define ins insert

#define debug(a) cerr<<(a)<<endl
#define dbrep(a,n) rep(_i,n) cerr<<(a[_i])<<" "; cerr<<endl
#define dbrep2(a,n,m) rep(_i,n){rep(_j,m) cerr<<(a[_i][_j])<<" "; cerr<<endl;}

using namespace std;

template<class A, class B>
ostream &operator<<(ostream &os, const pair<A,B> &p){return os<<"("<<p.fi<<","<<p.se<<")";}
template<class A, class B>
istream &operator>>(istream &is, pair<A,B> &p){return is>>p.fi>>p.se;}

//-------------------------------------------------
//--Extended GCD
//-------------------------------------------------

ll extgcd(ll a, ll b, ll &x, ll &y)
{
    if (b==0){
        x = 1; y = 0;
        return a;
    }
    ll d = extgcd(b,a%b,y,x);
    y -= a/b*x;
    return d;
}


//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t; cin>>t;
    while(t--){
        ll N,S,K; cin>>N>>S>>K;
        ll g = __gcd(K,N);
        if (S%g!=0){
            cout<<"-1\n";
            continue;
        }
        N/=g; S/=g; K/=g;
        ll inv,_;
        extgcd(K,N,inv,_);
        inv=(inv+N)%N;
        cout<<inv*(N-S)%N<<"\n";
    }
    return 0;
}
