题目描述

令 $f(a)$ 为最大的 $kin[1,n)$，满足前 $k$ 个数的 gcd 大于前 $k+1$ 个数的 gcd；若不存在则为 0。令 $g(a)$ 为对数组任意重排后 $f$ 的最大值。给定数组，要求对每个前缀分别输出其 $g$ 值。

输入格式

第一行包含整数 $t$。每组数据先给出 $n$，再给出长度为 $n$ 的数组 $a$。

输出格式

对每组数据输出 $n$ 个整数，第 $i$ 个为前缀 $[a_1,ldots,a_i]$ 的 $g$ 值。

样例

3
8
2 4 3 6 5 7 8 6
6
6 6 6 6 6 6
9
8 4 2 6 3 9 5 7 8

0 1 2 3 3 3 4 5
0 0 0 0 0 0
0 1 2 2 4 4 4 4 5

数据范围

本题来自 Codeforces Round 1050 (Div. 4)，原题编号 CF2148G，英文题名 Farmer John's Last Wish。