#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


////////////////////////////////////////////////////////////////////////////////
// 2^61 - 1 = 2'305'843'009'213'693'951
struct ModLong61 {
  static constexpr unsigned long long M = (1ULL << 61) - 1;
  unsigned long long x;
  constexpr ModLong61() : x(0ULL) {}
  constexpr ModLong61(unsigned x_) : x(x_) {}
  constexpr ModLong61(unsigned long long x_) : x(x_ % M) {}
  constexpr ModLong61(int x_) : x((x_ < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
  constexpr ModLong61(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
  ModLong61 &operator+=(const ModLong61 &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
  ModLong61 &operator-=(const ModLong61 &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
  ModLong61 &operator*=(const ModLong61 &a) {
    const unsigned __int128 y = static_cast<unsigned __int128>(x) * a.x;
    x = (y >> 61) + (y & M);
    x = (x >= M) ? (x - M) : x;
    return *this;
  }
  ModLong61 &operator/=(const ModLong61 &a) { return (*this *= a.inv()); }
  ModLong61 pow(long long e) const {
    if (e < 0) return inv().pow(-e);
    ModLong61 a = *this, b = 1ULL; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
  }
  ModLong61 inv() const {
    unsigned long long a = M, b = x; long long y = 0, z = 1;
    for (; b; ) { const unsigned long long q = a / b; const unsigned long long c = a - q * b; a = b; b = c; const long long w = y - static_cast<long long>(q) * z; y = z; z = w; }
    assert(a == 1ULL); return ModLong61(y);
  }
  ModLong61 operator+() const { return *this; }
  ModLong61 operator-() const { ModLong61 a; a.x = x ? (M - x) : 0ULL; return a; }
  ModLong61 operator+(const ModLong61 &a) const { return (ModLong61(*this) += a); }
  ModLong61 operator-(const ModLong61 &a) const { return (ModLong61(*this) -= a); }
  ModLong61 operator*(const ModLong61 &a) const { return (ModLong61(*this) *= a); }
  ModLong61 operator/(const ModLong61 &a) const { return (ModLong61(*this) /= a); }
  template <class T> friend ModLong61 operator+(T a, const ModLong61 &b) { return (ModLong61(a) += b); }
  template <class T> friend ModLong61 operator-(T a, const ModLong61 &b) { return (ModLong61(a) -= b); }
  template <class T> friend ModLong61 operator*(T a, const ModLong61 &b) { return (ModLong61(a) *= b); }
  template <class T> friend ModLong61 operator/(T a, const ModLong61 &b) { return (ModLong61(a) /= b); }
  explicit operator bool() const { return x; }
  bool operator==(const ModLong61 &a) const { return (x == a.x); }
  bool operator!=(const ModLong61 &a) const { return (x != a.x); }
  friend std::ostream &operator<<(std::ostream &os, const ModLong61 &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////

#include <chrono>

#ifdef LOCAL
mt19937_64 rng(58);
#else
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#endif

// [l, r]
Int randLong(Int l, Int r) {
  return uniform_int_distribution<Int>(l, r)(rng);
}
// const ModLong61 BASE = randLong(0, ModLong61::M - 1);

////////////////////////////////////////////////////////////////////////////////


bool solve(const vector<vector<int>> &stacks) {
  int lens[2];
  for (int i = 0; i < 2; ++i) {
    lens[i] = stacks[i].size();
  }
  const int N = (lens[0] + lens[1]) / 2;
  vector<ModLong61> rnds(N);
  for (int u = 0; u < N; ++u) {
    rnds[u] = randLong(0, ModLong61::M - 1);
  }
  vector<pair<unsigned long long, int>> h1s;
  {
    ModLong61 h;
    for (int j = 0; ; j += 2) {
      h1s.emplace_back((-h).x, -j);
      if (j + 2 <= lens[1]) {
        h += rnds[stacks[1][j]];
        h -= rnds[stacks[1][j + 1]];
      } else {
        break;
      }
    }
  }
  sort(h1s.begin(), h1s.end());
  int ls[2] = {};
  {
    ModLong61 h;
    for (int j = 0; ; j += 2) {
      auto it = lower_bound(h1s.begin(), h1s.end(), make_pair(h.x, -lens[1]));
      if (it != h1s.end() && it->first == h.x) {
        chmax(ls[0], j);
        chmax(ls[1], -it->second);
      }
      if (j + 2 <= lens[0]) {
        h += rnds[stacks[0][j]];
        h -= rnds[stacks[0][j + 1]];
      } else {
        break;
      }
    }
  }
  int rs[2] = {lens[0], lens[1]};
  for (; ls[0] < rs[0] && ls[1] < rs[1] && stacks[0][rs[0] - 1] == stacks[1][rs[1] - 1]; ) {
    --rs[0];
    --rs[1];
  }
  vector<vector<int>> rems(2);
  for (int i = 0; i < 2; ++i) {
    for (int j = ls[i]; j < rs[i]; ) {
      if ((j - ls[i]) % 2 != 0 && j + 1 < rs[i] && stacks[i][j] == stacks[i][j + 1]) {
        j += 2;
      } else {
        rems[i].push_back(stacks[i][j]);
        j += 1;
      }
    }
  }
  reverse(rems[1].begin(), rems[1].end());
  return (rems[0] != rems[1]);
}


map<pair<vector<vector<int>>, int>, bool> cache;
bool brute(const vector<vector<int>> &stacks, int taken) {
  const auto key = make_pair(stacks, taken);
  auto it = cache.find(key);
  if (it != cache.end()) return it->second;
  int sz = 0;
  for (int i = 0; i < (int)stacks.size(); ++i) sz += (int)stacks[i].size();
  for (int i = 0; i < (int)stacks.size(); ++i) if (stacks[i].size()) {
    if (sz % 2 == 0 && (taken & 1 << stacks[i].back())) return cache[key] = true;
    auto s = stacks;
    s[i].pop_back();
    if (!brute(s, (sz % 2 == 0) ? (taken | 1 << stacks[i].back()) : taken)) return cache[key] = true;
  }
  return cache[key] = false;
}

void expr() {
  for (int n = 1; n <= 6; ++n) {
    for (int k = 0; k <= 2 * n; ++k) {
      vector<int> perm(2 * n);
      for (int i = 0; i < 2 * n; ++i) perm[i] = i / 2;
      do {
        {
          bool ok = true;
          int mx = -1;
          for (int j = 0; j < 2 * n; ++j) {
            ok = ok && (mx + 1 >= perm[j]);
            chmax(mx, perm[j]);
          }
          if (!ok) {
            continue;
          }
        }
        
        const vector<vector<int>> stacks{
          vector<int>(perm.begin(), perm.begin() + k),
          vector<int>(perm.begin() + k, perm.end()),
        };
        const int lens[2] = {k, 2 * n - k};
        const bool brt = brute(stacks, 0);
        
        const bool slv = solve(stacks);
        if (brt != slv) {
          cerr << "FAIL " << stacks << ": " << brt << " " << slv << endl;
        }
        assert(brt == slv);
        
        // torikaesanaito owari
        if (lens[0] && lens[1] && stacks[0].back() == stacks[1].back()) {
          auto s = stacks;
          s[0].pop_back();
          s[1].pop_back();
          assert(brt == brute(s, 0));
          continue;
        }
        
        int ma[2] = {0, 0};
        {
          vector<pair<int, int>> m0m1s;
          for (int m0 = 0; m0 <= lens[0]; m0 += 2) for (int m1 = 0; m1 <= lens[1]; ++m1) {
            int ps[2] = {};
            for (int j = 0; j < m0; ++j) ps[j & 1] |= 1 << stacks[0][j];
            for (int j = 0; j < m1; ++j) ps[j & 1] |= 1 << stacks[1][j];
            if (ps[0] == ps[1]) {
              m0m1s.emplace_back(m0, m1);
            }
          }
          for (const auto &m0m1 : m0m1s) {
            if (make_pair(ma[0], ma[1]) < m0m1) {
              ma[0] = m0m1.first;
              ma[1] = m0m1.second;
            }
          }
          for (const auto &m0m1 : m0m1s) {
            assert(ma[0] >= m0m1.first);
            assert(ma[1] >= m0m1.second);
          }
        }
        
        // matching
        if (ma[0] == lens[0] && ma[1] == lens[1]) {
          assert(!brt);
          continue;
        }
        
        // reverse sugoi -> matching
        // assert OK but skip this check
        /*
        if (lens[0] - ma[0] == lens[1] - ma[1]) {
          const int r = lens[0] - ma[0];
          bool rev = true;
          for (int j = 0; j < r; ++j) {
            rev = rev && (stacks[0][lens[0] - 1 - j] == stacks[1][lens[1] - r + j]);
          }
          if (rev) {
            assert(r % 2 != 0);
            assert(!brt);
            continue;
          }
        }
        */
        
        if (ma[0] || ma[1]) {
          const vector<vector<int>> s{
            vector<int>(stacks[0].begin() + ma[0], stacks[0].end()),
            vector<int>(stacks[1].begin() + ma[1], stacks[1].end()),
          };
          assert(brt == brute(s, 0));
          continue;
        }
        
        // assert OK but skip this check
        /*
        vector<vector<int>> reduced(2);
        for (int i = 0; i < 2; ++i) {
          for (int j = 0; j < lens[i]; ++j) {
            if (reduced[i].size() && reduced[i].back() == stacks[i][j]) {
              reduced[i].pop_back();
            } else {
              reduced[i].push_back(stacks[i][j]);
            }
          }
        }
        const int red = brute(reduced, 0);
        if (stacks == reduced) {
          if (!brt) {
            cerr << stacks << ": " << brt << endl;
          }
          assert(brt);
          continue;
        }
        
        // sente can reduce
        if (red) {
          assert(brt);
          continue;
        }
        */
        
        /*
        if (!brt) {
          // cout << stacks << ": " << brt << endl;
          for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < lens[i]; ++j) {
              cout << stacks[i][j];
            }
            cout << '\n';
          }
          cout << endl;
        }
        */
        
        {
          vector<vector<int>> rems(2);
          for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < lens[i]; ) {
              if (j % 2 != 0 && j + 1 < lens[i] && stacks[i][j] == stacks[i][j + 1]) {
                j += 2;
              } else {
                rems[i].push_back(stacks[i][j]);
                j += 1;
              }
            }
          }
          reverse(rems[1].begin(), rems[1].end());
          if (rems[0] == rems[1]) {
            assert(!brt);
            continue;
          }
        }
        assert(brt);
      } while (next_permutation(perm.begin(), perm.end()));
    }
    cerr << "DONE n = " << n << ": |cache| = " << cache.size() << endl;
  }
}

int main() {
  // expr();
  
  for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
    int lens[2];
    scanf("%d%d", &lens[0], &lens[1]);
    vector<vector<int>> stacks(2);
    for (int i = 0; i < 2; ++i) {
      stacks[i].resize(lens[i]);
      for (int j = 0; j < lens[i]; ++j) {
        scanf("%d", &stacks[i][j]);
        --stacks[i][j];
      }
    }
    
    const bool ans = solve(stacks);
    puts(ans ? "1" : "2");
  }
#ifndef LOCAL
  break;
#endif
  }
  return 0;
}