package main

import (
	"bufio"
	"os"
	"sort"
)

type Item struct {
	val int
	pos int
}

func readInt(reader *bufio.Reader) int {
	var res int
	var b byte
	var err error
	for {
		b, err = reader.ReadByte()
		if err != nil {
			return 0
		}
		if b >= '0' && b <= '9' {
			res = int(b - '0')
			break
		}
	}
	for {
		b, err = reader.ReadByte()
		if err != nil {
			break
		}
		if b >= '0' && b <= '9' {
			res = res*10 + int(b-'0')
		} else {
			break
		}
	}
	return res
}

func writeInt(writer *bufio.Writer, n int) {
	if n == 0 {
		writer.WriteByte('0')
		return
	}
	var buf [20]byte
	i := 19
	for n > 0 {
		buf[i] = byte(n%10 + '0')
		n /= 10
		i--
	}
	writer.Write(buf[i+1:])
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	t := readInt(reader)
	for tc := 0; tc < t; tc++ {
		n := readInt(reader)
		items := make([]Item, n)
		for i := 0; i < n; i++ {
			items[i] = Item{val: readInt(reader), pos: i}
		}

		sort.Slice(items, func(i, j int) bool {
			g1 := items[i].val / 4
			g2 := items[j].val / 4
			if g1 == g2 {
				return items[i].val < items[j].val
			}
			return g1 < g2
		})

		ans := make([]int, n)
		pos := make([]int, 0, n)

		for i := 0; i < n; {
			j := i
			g := items[i].val / 4
			for j < n && items[j].val/4 == g {
				j++
			}

			pos = pos[:0]
			for k := i; k < j; k++ {
				pos = append(pos, items[k].pos)
			}
			sort.Ints(pos)

			for k := i; k < j; k++ {
				ans[pos[k-i]] = items[k].val
			}

			i = j
		}

		for i := 0; i < n; i++ {
			if i > 0 {
				writer.WriteByte(' ')
			}
			writeInt(writer, ans[i])
		}
		writer.WriteByte('\n')
	}
}