#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define li long int
#define ull unsigned long long
#define nL “\n”
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define a first
#define b second
#define vi vector
#define all(x) (x).begin(), (x).end()
#define umap unordered_map
#define uset unordered_set
#define f(i, n) for(i=0; i<n; i++)
#define F(i, k, n) for(i=k; i<n; i++)
#define imax INT_MAX
#define imin INT_MIN
#define exp 1e9
#define sz(x) (int((x).size()))
#define MOD 1000000007
#define int long long int
const int N = 100005;
int merge(int arr[], int start, int mid, int end)
{
int i = start;
int j = mid + 1;
int k = 0;
int temp[end-start+1];
int inv = 0;
while (i <= mid && j <= end)
{
if (arr[i] <= arr[j])
{
temp[k++] = arr[i++];
}
else
{
temp[k++] = arr[j++];
inv += (mid - i + 1);
}
}
while (i <= mid)
{
temp[k++] = arr[i++];
}
while (j <= end)
{
temp[k++] = arr[j++];
}
for (int i = start; i <= end; i++)
{
arr[i] = temp[i-start];
}
return inv;
}
int mergeSort(int arr[], int start, int end)
{
if (start >= end)
return 0;
int mid = start + (end - start) / 2;
int inv = 0;
inv += mergeSort(arr, start, mid);
inv += mergeSort(arr, mid + 1, end);
inv += merge(arr, start, mid, end);
return inv;
}
void solve()
{
int n;
cin >> n;
int arr[n];
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
int inv = mergeSort(arr, 0, n - 1);
cout << "Inversion Count = " << inv << nL;
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll t;
cin >> t;
while (t--)
{
solve();
cout << nL;
}
return 0;
}