#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define ti3 tuple<int,int,int>
#define mat vector<vector<int>>
const int inf = 1 << 30;
const ll linf = 1LL << 62;
const db EPS = 1e-7;
template<class T> void chmin(T& x, T y){if(x > y) x = y;}
template<class T> void chmax(T& x, T y){if(x < y) x = y;}

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

void solve(){
    ll X, Y, P, Q;
    cin >> X >> Y >> P >> Q;
    ll ans = linf;
    for(ll i = 0; i < Y; i++){
        for(ll j = 0; j < Q; j++){
            ll x, y;
            ll g = extgcd(2LL * (X + Y), P + Q, x, y);
            if((P + j - X - i) % g == 0){
                y *= (P + j - X - i) / g;
                y %= (X + Y) * 2LL / g;
                if(y > 0) y -= (X + Y) * 2LL / g;
                ans = min(ans, -y * (P + Q) + P + j);
            }
        }
    }
    if(ans == linf) cout << "infinity" << endl;
    else cout << ans << endl;
}

int main(){
    int T;
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
template<class S, class T> inline S max_L(S a,T b){
  return a>=b?a:b;
}
inline int my_getchar_unlocked(){
  static char buf[1048576];
  static int s = 1048576;
  static int e = 1048576;
  if(s == e && e == 1048576){
    e = fread_unlocked(buf, 1, 1048576, stdin);
    s = 0;
  }
  if(s == e){
    return EOF;
  }
  return buf[s++];
}
inline void rd(int &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = my_getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = my_getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
struct MY_WRITER{
  char buf[1048576];
  int s;
  int e;
  MY_WRITER(){
    s = 0;
    e = 1048576;
  }
  ~MY_WRITER(){
    if(s){
      fwrite_unlocked(buf, 1, s, stdout);
    }
  }
}
;
MY_WRITER MY_WRITER_VAR;
void my_putchar_unlocked(int a){
  if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
    fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
    MY_WRITER_VAR.s = 0;
  }
  MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
}
inline void wt_L(char a){
  my_putchar_unlocked(a);
}
inline void wt_L(long long x){
  int s=0;
  int m=0;
  char f[20];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    my_putchar_unlocked('-');
  }
  while(s--){
    my_putchar_unlocked(f[s]+'0');
  }
}
template<class S, class T> inline S chmin(S &a, T b){
  if(a>b){
    a=b;
  }
  return a;
}
int N;
int X[20];
int Y[20];
int Z[20];
long long dp[131072][17];
int main(){
  int i, mask;
  rd(N);
  {
    int Lj4PdHRW;
    for(Lj4PdHRW=(0);Lj4PdHRW<(N);Lj4PdHRW++){
      rd(X[Lj4PdHRW]);
      rd(Y[Lj4PdHRW]);
      rd(Z[Lj4PdHRW]);
    }
  }
  for(i=(0);i<(1<<N);i++){
    int j;
    for(j=(0);j<(N);j++){
      dp[i][j] = 4611686016279904256LL;
    }
  }
  dp[0][0] = 0;
  for(mask=(0);mask<(1<<N);mask++){
    for(i=(0);i<(N);i++){
      if(dp[mask][i] < 4611686016279904256LL){
        int j;
        for(j=(0);j<(N);j++){
          if(!((mask) &(1<<(j)))){
            chmin(dp[mask|(1<<j)][j], dp[mask][i] + abs(X[i]-X[j]) + abs(Y[i]-Y[j]) +max_L(Z[j]-Z[i], 0));
          }
        }
      }
    }
  }
  wt_L(dp[(1<<N)-1][0]);
  wt_L('\n');
  return 0;
}
// cLay varsion 20201018-1

// --- original code ---
// int N, X[20], Y[20], Z[20];
// ll dp[131072][17];
// {
//   rd(N,(X,Y,Z)(N));
//   rep(i,1<<N) rep(j,N) dp[i][j] = ll_inf;
//   dp[0][0] = 0;
//   rep(mask,1<<N) rep(i,N) if(dp[mask][i] < ll_inf) rep(j,N) if(!BIT_ith(mask,j)){
//     dp[mask|(1<<j)][j] <?= dp[mask][i] + abs(X[i]-X[j]) + abs(Y[i]-Y[j]) + max(Z[j]-Z[i], 0);
//   }
//   wt(dp[(1<<N)-1][0]);
// }
