# include <bits/stdc++.h>
# ifndef ngng628_library
# define ngng628_library
# define int long long
# define float long double
# define fi first
# define se second
# define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
# define reps(i,n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
# define rrep(i,n) for(int i=((int)(n)-1); i>=0; --i)
# define rreps(i,n) for(int i=((int)(n)); i>0; --i)
# define repr(i,b,e) for(int i=(b), i##_len=(e); i<i##_len; ++i)
# define reprs(i,b,e) for(int i=(b), i##_len=(e); i<=i##_len; ++i)
# define all(x) std::begin(x), std::end(x)
# define rall(x) std::rbegin(x), std::rend(x)
# define pb push_back
# define eb emplace_back
# define len(x) ((int)(x).size())
# define contains(x,key) ((x).find(key) != (x).end())
# define lb(v,x) distance(std::begin(v), lower_bound(all(v), (x)))
# define ub(v,x) distance(std::begin(v), upper_bound(all(v), (x)))
using namespace std;
template<class T> using vec = vector<T>;
using pii = pair<int, int>;
using vi = vec<int>;
using vb = vec<bool>;
using vvb = vec<vb>;
using vvvb = vec<vvb>;
using vs = vec<string>;
using vvi = vec<vi>;
using vvvi = vec<vvi>;
constexpr int INF = (1LL<<62)-(1LL<<31);
constexpr float EPS = 1e-10;
template<class T> istream& operator>>(istream& is, vec<T>& v) { for (auto& x : v) is >> x; return is; }
template<class T, class U> istream& operator>>(istream& is, pair<T, U>& p) { return is >> p.fi >> p.se; }
template<class T> T scan() { T ret; cin >> ret; return ret; }
template<class T> string join(const vec<T> &v){ stringstream s; rep (i, len(v)) s<<' '<<v[i]; return s.str().substr(1); }
template<class T> ostream& operator<<(ostream& os, const vec<T>& v){ if (len(v)) os << join(v); return os; }
template<class T> ostream& operator<<(ostream& os, const vec<vec<T>>& v){ rep (i, len(v)) { if (len(v[i])) os << join(v[i]) << (i-len(v)+1 ? "\n" : ""); } return os; }
template<class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p){ cout << p.fi << " " << p.se; return os; }
void print(){ cout << "\n"; }
template<class T, class... A>void print(const T& v, const A&...args){cout << v; if(sizeof...(args))cout << " "; print(args...);}
void eprint() { cerr << "\n"; }
template<class T, class... A>void eprint(const T& v, const A&...args){cerr << v; if(sizeof...(args))cerr << " "; eprint(args...);}
void drop(){ cout << "\n"; exit(0); }
template<class T, class... A>void drop(const T& v, const A&...args){cout << v; if(sizeof...(args))cout << " "; drop(args...);}
template<class T> inline constexpr bool chmax(T &a, const T& b) { return a < b && (a = b, true); }
template<class T> inline constexpr bool chmin(T &a, const T& b) { return a > b && (a = b, true); }
constexpr int ctoi(const char c) { return ('0' <= c and c <= '9') ? (c - '0') : -1; }
const char* yn(bool b) { return b ? "Yes" : "No"; }
# endif  // ngng628_library

struct Edge {
   Edge() = default;
   Edge(int t, int w, int k) : to(t), weight(w), K(k) {}
   int to, weight, K;
};
using Graph = vec<vec<Edge>>;

vi dijkstra(const Graph& graph, int start) {
   vi dist(len(graph), INF);
   priority_queue<pii, vec<pii>, greater<pii>> pq; // {dist, to}
   dist[start] = 0;
   pq.emplace(dist[start], start);
   while (not pq.empty()) {
      auto [d, now] = pq.top(); pq.pop();
      if (dist[now] < d) continue;
      for (auto& edge : graph[now]) {
         int loss = (-dist[now] % edge.K + edge.K) % edge.K;
         int cost = dist[now] + loss + edge.weight;
         if (chmin(dist[edge.to], cost)) {
            pq.emplace(cost, edge.to);
         }
      }
   }
   return dist;
}

int32_t main() {
   int n, m, x, y;
   cin >> n >> m >> x >> y;
   x--; y--;
   Graph g(n);
   rep (i, m) {
      int a, b, t, k;
      cin >> a >> b >> t >> k;
      a--; b--;
      g[a].eb(b, t, k);
      g[b].eb(a, t, k);
   }
   auto d = dijkstra(g, x);
   print(d[y] < INF ? d[y] : -1);
}

#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <bitset>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
clock_t __my_start_clock = clock();
#else
#define eprintf(...)
#endif

#define TIMESTAMP(x) eprintf("["#x"] Time : %.3lf s.\n", (clock() - __my_start_clock)*1.0/CLOCKS_PER_SEC)
#define TIMESTAMPf(x,...) eprintf("[" x "] Time : %.3lf s.\n", __VA_ARGS__, (clock() - __my_start_clock)*1.0/CLOCKS_PER_SEC)

using namespace std;

#ifdef LOCAL
static struct __timestamper {
  string what;
  __timestamper(const char* what) : what(what){};
  __timestamper(const string& what) : what(what){};
  ~__timestamper(){
    TIMESTAMPf("%s", what.data());
	}
} __TIMESTAMPER("end");
#else 
struct __timestamper {};
#endif

typedef long long ll;
typedef long double ld;

void solve() {
  int n;
  string a, b, c;
  cin >> n >> a >> b >> c;
  eprintf("%d\n%s\n%s\n%s\n", n, a.c_str(), b.c_str(), c.c_str());
  a = a + a;
  b = b + b;
  c = c + c;
  auto test_one = [](const string& a, const string& b) {
    int pt = 0;
    for (char c : a) {
      if (b[pt] == c) pt++;
      if (pt == (int)b.size()) return true;
    }
    return false;
  };
  auto test = [&](const string &t) {
    return test_one(a, t) && test_one(b, t) && test_one(c, t);
  };

  for (char c1 = '0'; c1 <= '1'; c1++) {
    for (char c2 = '0'; c2 <= '1'; c2++) {
      for (char c3 = '0'; c3 <= '1'; c3++) {
        string cand = string(n, c1) + c2 + string(n, c3);
        if (test(cand)) {
          printf("%s\n", cand.c_str());
          return;
        }
        cand = string(n, c1) + string(n, c3) + c2;
        if (test(cand)) {
          printf("%s\n", cand.c_str());
          return;
        }
        cand = c2 + string(n, c1) + string(n, c3);
        if (test(cand)) {
          printf("%s\n", cand.c_str());
          return;
        }
      }
    }
  }
  assert(false);
}

int main() {
#ifdef LOCAL
  freopen("a.in", "r", stdin);
  freopen("a.out", "w", stdout);
#endif

  int t;
  cin >> t;
  while (t-->0) {
    solve();
  }

  return 0;
}
