#include <stdio.h>
#include <stdlib.h>

int tPow(int n) {
    int result = 1;
    for(int i=0;i<n;i++) result *= 10;
    return result;
}

void print(int *t, int n) {
    for(int i=0;i<n;i++) printf("%d\n",t[i]);
}

void countingSort(int *t, int n, int k) {
    int *B = malloc(n*sizeof(int));
    int C[10];

    print(t,n);
    for(int i=0;i<10;i++) C[i] = 0;
    for(int i=0;i<n;i++) C[ (t[i]/tPow(k))%10 ]++;
    for(int i=0;i<10;i++) C[i] += C[i-1];
    for(int i=n-1;i>=0;i--) {
        C[  (t[i]/tPow(k))%10 ]--;
        B[ C[ (t[i]/tPow(k))%10 ] ] = t[i];
    }
    for(int i=0;i<n;i++) t[i] = B[i];
    print(t,n);
    free(B);
    free(C);
}

void Radixsort(int *t, int n, int k) {
    for(int i=0;i<k;i++) countingSort(t,n,i);
}

int main(void) {
    int Z, n, k;
    scanf("%d",&Z);
    for(int i=0;i<Z;i++) {
        scanf("%d%d",&n,&k);
        int *t = malloc(n*sizeof(int));
        for(int j=0;j<n;j++) scanf("%d",&t[j]);
        print(t,n);
        Radixsort(t,n,k);
        print(t,n);
        free(t);
    }
}