Rearrangement for Divisibility

You are given an array of N positive integers. Your task is to determine whether it is possible to rearrange the array into a new array C such that for every adjacent pair of elements, i.e. for all indices \(1 \le i < N\), at least one of the two numbers divides the other. In other words, the following condition must hold:

[ \forall, 1 \le i < N, \quad \text{either} \quad C_{i} \mid C_{i+1} \quad \text{or} \quad C_{i+1} \mid C_{i} ]

If a valid rearrangement exists, output "YES" and the rearranged array (using the sorted order in this simplified version). Otherwise, output "NO".

Note: In this problem, it is assumed that simply sorting the array provides a valid rearrangement.

inputFormat

The input is read from standard input (stdin). The first line contains an integer T, the number of test cases. For each test case, the first line contains an integer N, representing the number of elements in the array. The second line contains N space-separated integers representing the array elements.

outputFormat

For each test case, if a valid rearrangement exists, output "YES" on the first line and the rearranged array (space-separated) on the second line. Otherwise, output "NO".## sample

1
3
3 6 9

YES
3 6 9