D. GCD in Median Land
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of $$$n$$$ integers.

For each integer $$$k$$$ from $$$1$$$ to $$$n$$$, solve the following problem:

  • Select a $$$k$$$ length subsequence of $$$a$$$ and take its median.
  • Do it for all possible $$$k$$$ length subsequences of $$$a$$$ and compute the medians of each of the subsequences.
  • Now compute the Greatest Common Divisor (GCD) of all those medians.

Check the sample explanation for more clarity.

A subsequence is a sequence that can be derived from the given array by deleting zero or more elements without changing the order of the remaining elements.

The median of a sequence is the value of the element which is in the middle of the sequence after sorting it in non-decreasing order. If the length of the sequence is even, the left of the two middle elements is used.

For example, for the sequence $$$[4,2,7,5]$$$, its median is $$$4$$$ since after sorting the sequence, it will look like $$$[2,4,5,7]$$$ and the left of two middle elements is equal to $$$4$$$. The median of $$$[7,1,2,9,6]$$$ equals $$$6$$$ since after sorting, the value $$$6$$$ will be in the middle of the sequence.

Input

The first line contains an integer $$$t (1\leq t\leq 10^5)$$$, the number of test cases.

The first line of each test case contains an integer $$$n(1\leq n\leq 10^5)$$$  — the number of integers in the array. The next line contains $$$n$$$ space-separated integers $$$a_i (1\leq a_i\leq 10^9)$$$  — the elements of the array.

The sum of $$$n$$$ over all test cases doesn't exceed $$$5\cdot 10^5$$$.

Don't forget to use Fast I/O as the input is huge.

Output

For each test case, print $$$n$$$ space-separated integers in a line. The $$$k^{th}$$$ integer will represent the $$$\operatorname{GCD}$$$ of the medians of all possible $$$k$$$ length subsequences of $$$a$$$.

Example
Input
2
3
12 8 30
2
5 7
Output
2 4 12 
1 5
Note

In the first test case,

The $$$1$$$ length subsequences and their medians are:

  1. $$$[12]$$$. Median = $$$12$$$.
  2. $$$[8]$$$. Median = $$$8$$$.
  3. $$$[30]$$$. Median = $$$30$$$.

The $$$\operatorname{GCD}$$$ of the medians $$$=\operatorname{GCD}([12,8,30]) = 2$$$.

The $$$2$$$ length subsequences and their medians are:

  1. $$$[12, 8]$$$. After sorting: $$$[8, 12]$$$. Median = $$$8$$$.
  2. $$$[8, 30]$$$. After sorting: $$$[8, 30]$$$. Median = $$$8$$$.
  3. $$$[12, 30]$$$. After sorting: $$$[12, 30]$$$. Median = $$$12$$$.

The $$$\operatorname{GCD}$$$ of the medians $$$=\operatorname{GCD}([8, 8, 12])=4$$$.

The $$$3$$$ length subsequences and their medians are:

  1. $$$[12, 8, 30]$$$. After sorting: $$$[8, 12, 30]$$$. Median = $$$12$$$.
The $$$\operatorname{GCD}$$$ of the medians $$$=\operatorname{GCD}([12])=12$$$.