t = int(input())

for tc in range(t):
    n, k = map(int, input().split())

    cards = list(map(int, input().split()))
    ct = {}

    ans = n

    for c in cards:
        if c in ct:
            ct.update({c: ct[c] + 1})
        else:
            ct.update({c: 1})
        if ct[c] >= k:
            ans = k - 1

    print(ans)

t = int(input())

for tc in range(t):
    n, m = map(int, input().split())
    gr = []

    for i in range(n):
        gr.append(input())

    ans = "YES"

    if gr[0][0] != gr[n - 1][m - 1]:

        impossible = True
        for j in range(m - 1):
            if gr[0][j] != gr[0][j + 1] or gr[n - 1][j] != gr[n - 1][j + 1]:
                impossible = False

        if impossible:
            ans = "NO"

        impossible = True
        for i in range(n - 1):
            if gr[i][0] != gr[i + 1][0] or gr[i][m - 1] != gr[i + 1][m - 1]:
                impossible = False

        if impossible:
            ans = "NO"

    print(ans)

t = int(input())

for tc in range(t):

    n = int(input())
    a = list(map(int, input().split()))

    maxsize = max(a)

    a.sort()
    mexsize = 1
    for sz in a:
        if sz == mexsize:
            mexsize = mexsize + 1

    if mexsize > maxsize:
        print("Alice" if maxsize % 2 == 1 else "Bob")
    else:
        print("Alice" if mexsize % 2 == 1 else "Bob")

t = int(input())

for tc in range(t):
    n, k = map(int, input().split())

    i = 0
    while (1 << (i + 1)) <= k:
        i = i + 1

    ans = [k - (1 << i), k + 1, k + 1 + (1 << i)]

    for j in range(20):
        if j != i:
            ans.append(1 << j);

    print(len(ans))
    print(*ans)

t = int(input())

for tc in range(t):
    n = int(input())
    s = input()
    mn = 0
    mx = 0
    cur = 0

    for c in s:

        if (cur % 2 == 0) == (c == '1'):
            cur = cur + 1
        else:
            cur = cur - 1

        mn = min(mn, cur)
        mx = max(mx, cur)

    print(mx - mn)

def getSubarraySums(a):

    cts = []
    for i in range(len(a)):
        sm = 0
        for j in range(i, len(a)):
            sm = sm + a[j]
            cts.append(sm)

    cts.sort()
    return cts

def getOddOccurringElements(cts):

    odds = []

    for ct in cts:
        if len(odds) > 0 and ct == odds[-1]:
            odds.pop()
        else:
            odds.append(ct)
    return odds

def getPalindrome(odds, n):

    a = [0] * n
    prev = 0
    idx = (n - 1) // 2
    
    for x in odds:
        if idx == n - 1 - idx:
            a[idx] = x
        else:
            a[idx] = (x - prev) // 2
            a[n - 1 - idx] = (x - prev) // 2
        prev = x
        idx = idx - 1
    
    return a

def getLargestExcluded(bigList, smallList):

    while len(smallList) > 0 and bigList[-1] == smallList[-1]:
        bigList.pop()
        smallList.pop()
    return bigList[-1]

t = int(input())

for tc in range(t):

    n = int(input())
    
    subarraySums = list(map(int, input().split()))
    subarraySums.sort()
    odds = getOddOccurringElements(subarraySums)
    
    missingSum = -1
    
    if len(odds) > (n + 1) // 2:
    
        oddvals = []
        evenvals = []
        for x in odds:
            if x % 2 == 1:
                oddvals.append(x)
            else:
                evenvals.append(x)

        if len(evenvals) > 0 and len(oddvals) > 0:

            missingSum = evenvals[0] if len(evenvals) == 1 else oddvals[0]

        else:

            b = getPalindrome(odds, n + 2)
            bSums = getSubarraySums(b)
            y = bSums[-1]
            x = getLargestExcluded(bSums, subarraySums)
            missingSum = 2 * x - y
    
    else:
        
        b = getPalindrome(odds, n - 2)
        bSums = getSubarraySums(b)
        y = bSums[-1]
        x = getLargestExcluded(subarraySums, bSums)
        missingSum = 2 * x - y

    odds.append(missingSum)
    odds.sort()
    odds = getOddOccurringElements(odds)
    
    ans = getPalindrome(odds, n)
    print(*ans)

n, m, k = map(int, input().split())
a = []

for i in range(n):
    a.append(list(map(int, input().split())))

ans = []

for x in range(n):
    for y in range(m):
        for z in range(1, n + 1):
            if y % 2 == 1:
                ans.append([x, y, z, a[x][y]])
            else:
                ans.append([x, y, z, a[min(x, n - z)][y]])
        for z in range(n + 1, n + k + 1):
            if y % 2 == 1:
                ans.append([x, y, z, a[x][y]])
            else:
                ans.append([x, y, z, z - n])

for x in range(n, n + k):
    for y in range(m):
        for z in range(1, n + 1):
            if y % 2 == 1:
                ans.append([x, y, z, x - n + 1])
            else:
                ans.append([x, y, z, a[n - z][y]])
        ans.append([x, y, n + 1, x - n + 1])

for y in range(m):
    for z in range(n + 2, n + k + 1):
        ans.append([n, y, z, z - n])

for x in range(n + 1, n + k):
    for z in range(n + 2, n + k + 1):
        ans.append([x, 0, z, max(x - n + 1, z - n)])

print(len(ans))

for cube in ans:
    print(cube[0] + 1, cube[1] + 1, cube[2] + 1, cube[3])

/**
 *    author:  tourist
 *    created: 26.11.2023 09:36:38       
**/
#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
 
const long long inf = (long long) 1e18;
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<long long> l(n), r(n);
  for (int i = 0; i < n; i++) {
    cin >> l[i] >> r[i];
  }
  int original_n = n;
  for (int rot = 0; rot < 2; rot++) {
    // make all left ends distinct
    map<long long, vector<long long>> mp;
    for (int i = 0; i < n; i++) {
      mp[l[i]].push_back(r[i]);
    }
    vector<long long> new_l, new_r;
    auto it = mp.begin();
    multiset<long long> s;
    long long T = -inf;
    while (true) {
      if (s.empty()) {
        if (it == mp.end()) {
          break;
        }
        T = it->first;
      }
      while (it != mp.end() && T == it->first) {
        s.insert(it->second.begin(), it->second.end());
        ++it;
      }
      assert(!s.empty());
      new_l.push_back(T);
      new_r.push_back(*s.begin());
      s.erase(s.begin());
      T += 1;
      while (!s.empty() && *s.begin() < T) {
        s.erase(s.begin());
      }
    }
    swap(l, new_l);
    swap(r, new_r);
    n = (int) l.size();
    for (int i = 0; i < n; i++) {
      l[i] *= -1;
      r[i] *= -1;
      swap(l[i], r[i]);
    }
  }
  sort(l.begin(), l.end());
  sort(r.begin(), r.end());
  vector<long long> ans(original_n + 1);
  long long lx = -inf, rx = -inf;
  int pl = 0, pr = 0;
  int k = 0;
  while (pl < n || pr < n) {
    long long wait = min(pl < n ? l[pl] - lx : inf, pr < n ? r[pr] - rx : inf);
    ans[k] += wait;
    lx += wait;
    rx += wait;
    while (pl < n && l[pl] == lx) {
      k += 1;
      lx += 1;
      pl += 1;
    }
    while (pr < n && r[pr] == rx) {
      ans[k] += 1;
      k -= 1;
      rx += 1;
      pr += 1;
    }
  }
  for (int i = n; i > 1; i--) {
    ans[i - 1] += ans[i];
  }
  for (int i = 1; i <= original_n; i++) {
    cout << ans[i] << '\n';
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {

    int t; cin >> t;
    for(int tc = 1; tc <= t; ++tc) {

        int n; cin >> n;
        int mn = INT_MAX, mx = INT_MIN;

        for(int i = 0; i < n; ++i) {
            int x; cin >> x;
            mn = min(mn, x);
            mx = max(mx, x);
        }

        if(mn < 0) cout << mn << '\n';
        else cout << mx << '\n';
    }
}

#include <bits/stdc++.h>
using namespace std;
#define N 200010

int idx[N];

int main() {

    int t; cin >> t;
    for(int tc = 1; tc <= t; ++tc) {

        int n; cin >> n;

        for(int i = 1; i <= n; ++i) {
            int x; cin >> x;
            idx[x] = i;
        }

        if(idx[n] < min(idx[1], idx[2])) {
            cout << idx[n] << ' ' << min(idx[1], idx[2]) << '\n';
        } else if(idx[n] > max(idx[1], idx[2])) {
            cout << idx[n] << ' ' << max(idx[1], idx[2]) << '\n';
        } else {
            cout << idx[1] << ' ' << idx[2] << '\n';
        }
    }
}

#include <bits/stdc++.h>
using namespace std;

int main() {

    int t; cin >> t;
    for(int tc = 1; tc <= t; ++tc) {

        int n, m; cin >> n >> m;

        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < m; ++j) {
                if(i % 2 == 0) cout << (n / 2 + i / 2) * m + j + 1 << ' ';
                else cout << (i / 2) * m + j + 1 << ' ';
            }
            cout << '\n';
        }
    }
}

#include <bits/stdc++.h>
using namespace std;

int main() {

    int n, q; string s;
    cin >> n >> q >> s;

    set<int> a;

    for(int i = 1; i <= n; ++i)
        if((i % 2) != (s[i - 1] == '('))
            a.insert(i);

    while(q--) {
        int i; cin >> i;

        if(a.count(i)) a.erase(i);
        else a.insert(i);

        if(n % 2) cout << "NO\n";
        else if(a.size() && (*a.begin() % 2 || !(*a.rbegin() % 2))) cout << "NO\n";
        else cout << "YES\n";
    }
}

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;

ll M = 1000000007;

ll pw(ll a, ll p) { return p ? pw(a * a % M, p / 2) * (p & 1 ? a : 1) % M : 1; }

ll inv(ll a) { return pw(a, M - 2); }

int main() {

    ll t; cin >> t;
    for(ll tc = 1; tc <= t; ++tc) {

        ll n, m, k, ai;
        cin >> n >> m >> k;
        for(ll i = 0; i < n; ++i) cin >> ai;

        ll ans = pw(k, m), mCi = 1;

        for(ll i = 0; i < n; ++i) {
            ans = (ans + M - mCi * pw(k - 1, m - i) % M) % M;
            mCi = mCi * (m - i) % M * inv(i + 1) % M;
        }

        cout << ans << '\n';
    }
}

#include <bits/stdc++.h>
using namespace std;

char grid[110][110];
int n;
vector<pair<int, int>> snake;
map<pair<int, int>, char> getChar = {
    {{1, 0}, 'v'},
    {{-1, 0}, '^'},
    {{0, 1}, '>'},
    {{0, -1}, '<'}
};

pair<pair<int, int>, char> getBeltAndDir(pair<int, int> p) {
    if(p.first == -1) return {p, 'X'};
    pair<int, int> q = p;

    if(p.first == 0) q.first++;
    if(p.second == 0) q.second++;
    if(p.first > n) q.first--;
    if(p.second > n) q.second--;

    return {q, getChar[{p.first - q.first, p.second - q.second}]};
}

pair<pair<int, int>, char> query(int idx) {

    cout << "? " << snake[idx].first << ' ' << snake[idx].second << endl;

    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j)
            cout << grid[i][j];
        cout << endl;
    }

    int i, j; cin >> i >> j;

    return getBeltAndDir({i, j});
}

void fillGrid() {
    for(int i = 0; i < n * n; ++i) {
        int dx = snake[i + 1].first - snake[i].first;
        int dy = snake[i + 1].second - snake[i].second;

        grid[snake[i].first][snake[i].second] = getChar[{dx, dy}];
    }
}

int main() {
    cin >> n;

    for(int i = 1; i <= n; ++i)
        if(i % 2 == 0)
            for(int j = n; j >= 1; --j)
                snake.emplace_back(i, j);
        else
            for(int j = 1; j <= n; ++j)
                snake.emplace_back(i, j);

    snake.emplace_back(n + 1, (n % 2 ? n : 1));
    fillGrid();

    auto ans = query(0);

    if(ans.second != 'X') {

        snake.pop_back();
        reverse(snake.begin(), snake.end());
        snake.emplace_back(0, 1);
        fillGrid();

        ans = query(0);
    }

    if(ans.second == 'X') {

        int id = 0;
        for(int j = 13; j >= 0; --j)
            if(id + (1 << j) < n * n && query(id + (1 << j)).second == 'X')
                id += (1 << j);

        ans.first = snake[id];

        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
                if(i < ans.first.first) grid[i][j] = '^';
                else if(i > ans.first.first) grid[i][j] = 'v';
                else grid[i][j] = j < ans.first.second ? '<' : '>';
            
        ans.second = query(id).second;
    }

    cout << "! " << ans.first.first << ' ' << ans.first.second << ' ' << ans.second << endl;
}

#include <bits/stdc++.h>
using namespace std;

int grid[45][45];

int main() {
    int num_tests;
    cin >> num_tests;

    for (int test = 0; test < num_tests; ++test) {
        int n, m;
        cin >> n >> m;

        int max_i = 0, max_j = 0;
        
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) {
                cin >> grid[i][j];
                if (grid[i][j] > grid[max_i][max_j])
                    max_i = i, max_j = j;
            }

        int h = max(max_i+1, n-max_i);
        int w = max(max_j+1, m-max_j);
        cout << h * w << '\n';
    }
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    int num_tests;
    cin >> num_tests;

    for (int test = 0; test < num_tests; ++test) {

        int n; cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; ++i)
            cin >> a[i];

        if (n % 2 == 1) {
            cout << "Mike\n";
            continue;
        }

        int smallest = 0;
        for (int i = 0; i < n; ++i)
            if (a[i] < a[smallest])
                smallest = i;

        if (smallest % 2 == 0) cout << "Joe\n";
        else cout << "Mike\n";
    }
}

#include <bits/stdc++.h>
using namespace std;

#define N 1010

int grid[N][N], mn[N][N], mx[N][N];

int main() {
    int num_tests;
    cin >> num_tests;

    for (int test = 0; test < num_tests; ++test) {
        int n, m;
        cin >> n >> m;
        
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
                cin >> grid[i][j];
        
        mn[0][0] = mx[0][0] = grid[0][0];
        
        for(int i = 1; i < n; ++i)
            mx[i][0] = mn[i][0] = mx[i - 1][0] + grid[i][0];
        
        for(int j = 1; j < m; ++j)
            mx[0][j] = mn[0][j] = mx[0][j - 1] + grid[0][j];
        
        for(int i = 1; i < n; ++i)
            for(int j = 1; j < m; ++j) {
                mx[i][j] = max(mx[i - 1][j], mx[i][j - 1]) + grid[i][j];
                mn[i][j] = min(mn[i - 1][j], mn[i][j - 1]) + grid[i][j];
            }
        
        if(mx[n - 1][m - 1] % 2 || mn[n - 1][m - 1] > 0 || mx[n - 1][m - 1] < 0)
            cout << "NO\n";
        else
            cout << "YES\n";
    }
}

#include <bits/stdc++.h>
using namespace std;

#define N 2010

vector<int> tree[N];

int dfs(int i, int p) {
    int sm = 0, z = 0;
    
    for (int j : tree[i]) if (j != p) {
        int x = dfs(j, i);
        sm += x;
        if (x == 0)
            z++;
    }
    
    return sm + max(0, z - 1);
}

int main() {
    int num_tests;
    cin >> num_tests;

    for (int test = 0; test < num_tests; ++test) {
        int n;
        cin >> n;
        
        for (int i = 1; i < n; ++i) {
            int u, v;
            cin >> u >> v;
            tree[u].push_back(v);
            tree[v].push_back(u);
        }
        
        if (n == 1)
            cout << "0\n";
        else {
            int ans = n;

            for (int i = 1; i <= n; ++i)
                ans = min(ans, 1 + dfs(i, i));
            
            cout << ans << '\n';
        }
        
        for (int i = 1; i <= n; ++i)
            tree[i].clear();
    }
}

#include <bits/stdc++.h>
using namespace std;

#define N 200010

vector<int> tree[N];

int dfs(int i, int p) {
    int sm = 0, z = 0;
    
    for (int j : tree[i]) if (j != p) {
        int x = dfs(j, i);
        sm += x;
        if (x == 0)
            z++;
    }
    
    return sm + max(0, z - 1);
}

int main() {
    int num_tests;
    cin >> num_tests;

    for (int test = 0; test < num_tests; ++test) {
        int n;
        cin >> n;
        
        for (int i = 1; i < n; ++i) {
            int u, v;
            cin >> u >> v;
            tree[u].push_back(v);
            tree[v].push_back(u);
        }

        int max_deg = 0;
        for (int i = 1; i <= n; ++i)
            max_deg = max(max_deg, (int)tree[i].size());
        
        if (max_deg == 0)
            cout << "0\n";
        else if (max_deg < 3)
            cout << "1\n";
        else {
            for (int i = 1; i <= n; ++i)
                if (tree[i].size() >= 3) {
                    cout << dfs(i, i) << '\n';
                    break;
                }
        }
        
        for (int i = 1; i <= n; ++i)
            tree[i].clear();
    }
}

#include <bits/stdc++.h>
using namespace std;

#define N 600010

vector<pair<int, int>> graph[N];
vector<int> lst;

int ans[2][N];

bool used[N], usedEdges[N];

void dfs(int i) {
    lst.push_back(i);

    if (!used[i]) {
        used[i] = true;
        
        for (pair<int, int> p : graph[i])
            if (!usedEdges[p.second]) {
                usedEdges[p.second] = true;
                dfs(p.first);
                lst.push_back(i);
            }
    }
}

int main() {

    int n; cin >> n;
    string ptop(n, 'U'), pbot(n, 'D');
    string mtop(n, 'U'), mbot(n, 'D');

    for (int i = 0; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u].emplace_back(v, i);
        graph[v].emplace_back(u, i);
    }

    int idx = 0;
    for (int i = 1; i <= 2 * n; ++i) if (!used[i]) {

        dfs(i);
        lst.pop_back();
        int k = lst.size() / 2;
        
        if (k == 1) {
            cout << "-1\n";
            exit(0);
        }

        for (int j = 0; j < k; ++j) {
            ans[0][j + idx] = lst[j];
            ans[1][j + idx] = lst[2 * k - 1 - j];
        }

        for (int j = 0; j < k - 1; j += 2)
            ptop[j + idx] = pbot[j + idx] = 'L', ptop[j + 1 + idx] = pbot[j + 1 + idx] = 'R';
        for (int j = 1; j < k - 1; j += 2)
            mtop[j + idx] = mbot[j + idx] = 'L', mtop[j + 1 + idx] = mbot[j + 1 + idx] = 'R';
        lst.clear();

        idx += k;
    }

    cout << "2 " << n << '\n';
    
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < n; ++j)
            cout << ans[i][j] << ' ';
        cout << '\n';
    }

    cout << ptop << '\n' << pbot << '\n';
    cout << mtop << '\n' << mbot << '\n';
}