#include <bits/stdc++.h>

#include <iostream>
//#include <algorithm>
// #include <iomanip>
#define ll long long
#define map unordered_map
#define set unordered_set
#define l_l pair<ll, ll>
#define vll vector<ll>
#define mll map<ll, ll>
#define mp make_pair

using namespace std;

const ll MOD = 1000000007LL;
const ll INF = (1LL << 60LL);

ll mod(ll a, ll m) {
  ll r = (a % m + m) % m;
  return r;
}

ll extGcd(ll a, ll b, ll &p, ll &q) {
  if (b == 0) {
    p = 1;
    q = 0;
    return a;
  }
  ll d = extGcd(b, a % b, q, p);
  q -= a / b * p;
  return d;
}

pair<ll, ll> crt(const vector<ll> &b, const vector<ll> &m) {
  ll r = 0, M = 1;
  for (int i = 0; i < (int)b.size(); ++i) {
    ll p, q;
    ll d = extGcd(M, m[i], p, q);
    if ((b[i] - r) % d != 0) {
      return make_pair(0, -1);
    }
    ll tmp = (b[i] - r) / d * p % (m[i] / d);
    r += M * tmp;
    M *= m[i] / d;
  }
  return make_pair(mod(r, M), M);
}

int main() {
  ll T;
  scanf("%lld", &T);

  for (ll i = 0; i < T; i++) {
    ll N, S, K;
    scanf("%lld %lld %lld", &N, &S, &K);

    auto r1 = crt({0, N - S}, {K, N});
    // cout << r1.second << "k+" << r1.first << endl;  // 15k + 8

    ll ans;
    if (r1.second <= 0) {
      ans = -1;
    } else {
      ans = r1.first / K;
    }
    cout << (ans) << endl;
    // cout << ("") << endl;
  }

  //
}

#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 3e5+10;
const int N = 3e5+10;
typedef long long ll;
struct node
{
int val,i;
bool operator<(node x)const {
	return val<x.val;
}
}sn[inf];
ll tree[inf],b[inf],n;
void add(int i,ll x)
{
while(i<=n){
	tree[i]+=x;
	i+=i&-i;
}
}
ll query(int i)
{
ll sum=0;
while(i>=1)
{
	sum+=tree[i];
	i-=i&-i;
}
return sum;
}
int pai[inf];
int main()
{
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>pai[i];
        pai[i]++;
        sn[i].val=pai[i];
        sn[i].i=i;
    }
    sort(sn+1,sn+n+1);
    int cnt=1;
    for(int i=1;i<=n;i++)
    {
        if(i>1&&sn[i].val>sn[i-1].val)
            cnt++;
        b[sn[i].i]=cnt;
    }
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        add(b[i],1);
        ans+=i-query(b[i]);
    }
    cout<<ans<<endl;
    for(int i = 1; i < n; i++ ){
        ll right = pai[i]-1;
        ll left;// = pai[i]+1;
        if(pai[i]==n)left = 0;
        else left = n - pai[i];
        ans = ans-right+left;
        cout<<ans<<endl;
    }
   // cout<<ans<<endl;
return 0;
}
