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

struct fastio{fastio(){cin.tie(nullptr);ios_base::sync_with_stdio(false);std::cout<<std::fixed<<setprecision(10);}}oitsaf;
#define rep(i,n) for(int i=0;i<int(n);++i)
constexpr char newl = '\n';
template<class T>std::istream&operator>>(std::istream&is,std::vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T>std::ostream&operator<<(std::ostream&os,std::vector<T>const&v){for(auto const& vi:v)os<<vi<<" ";return os;}
#if _local
struct debug_structure{template<class T>debug_structure&operator<<(const T&elm){std::cerr<<elm<<std::flush;return*this;}}dout;
#else
struct debug_structure{template<class T>debug_structure&operator<<(const T&elm){return*this;}}dout;
#endif
template<class T>inline bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  cin >> a;
  vector<int> S(2e6);
  set<int> st;
  rep(i, m) { S[a[i]]++; }
  rep(i, 2e6) if (S[i] == 0) st.emplace(i);
  int mex = 0;
  while (S[mex])
    mex++;
  int ans = mex;
  for (int i = m; i < n; ++i) {
    dout << mex << newl;
    S[a[i]]++;
    S[a[i - m]]--;
    if (S[a[i]] == 1) {
      st.erase(a[i]);
    }
    if (S[a[i - m]] == 0) {
      st.emplace(a[i - m]);
      if (chmin(mex, a[i - m])) {
        chmin(ans, mex);
      }
    }
    dout << mex << newl;
    if (S[a[i]] == 1 and a[i] == mex) {
      auto itr = st.upper_bound(mex);
      mex = *itr;
    }
  }
  cout << (ans) << endl;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, s, k;
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, x, y);
	ll t = x;
	x = y;
	y = t - (a / b) * y;
	return d;
}
void solve()
{
	cin >> n >> s >> k;
	ll x, y, d;
	if ((d = extgcd(k, n, x, y)) != 1ll)
	{
		if (s % d)
		{
			puts("-1");
			return ;
		}
		else
		{
			k /= d, n /= d, s /= d;
		}
	}
	x *= -s;
	y *= -s;
	cout << (x % n + n) % n << endl;
}
int main()
{
	int T;
	cin >> T;
	while (T--) solve();
	return 0;
}