Longest Divisible Subsequence

Given a list of integers, your task is to find the longest subsequence such that each element in the subsequence is divisible by the element immediately before it. In other words, for a subsequence \(a_1, a_2, \dots, a_k\), it must hold that \(a_i \mid a_{i+1}\) (i.e. \(a_{i+1} \% a_i = 0\)) for all \(2 \leq i \leq k\).

The subsequence must maintain the original order of elements as they appear in the input list. If there are multiple valid answers, you can output any of them.

inputFormat

The input begins with an integer \(T\) denoting the number of test cases. Each test case consists of two lines:

• The first line contains an integer \(N\), the number of elements in the list.
• The second line contains \(N\) space-separated integers.

outputFormat

For each test case, output a single line containing the longest divisible subsequence. The numbers should be space-separated. If there are multiple solutions, print any one of them.

## sample

1
4
3 6 7 12

3 6 12

</p>