This is the hard version of this problem. In this version, you are required to find the values of $$$f(\cdot)$$$ for each prefix of $$$a$$$.

For any array $$$[c_1, c_2, \ldots, c_m]$$$, we define $$$f(c)$$$ as the maximum possible $$$\operatorname{mex}(c)$$$$$$^{\text{∗}}$$$ that can be achieved by performing the following operation exactly once:

Choose an integer array $$$[b_1, b_2, \ldots, b_m]$$$ such that $$$b_i \ge 1$$$ for all $$$1 \le i \le m$$$;
Set $$$c_i := c_i \, \bmod \, b_i$$$$$$^{\text{†}}$$$ for every $$$1 \le i \le m$$$.

You are given an array $$$a$$$ consisting of $$$n$$$ non-negative integers. For each prefix $$$a^{(i)} = [a_1, a_2, \ldots, a_i]$$$, determine the value of $$$f(a^{(i)})$$$.

$$$^{\text{∗}}$$$$$$\operatorname{mex}(c)$$$ denotes the minimum excluded (MEX) of the integers in $$$c$$$. For example, $$$\operatorname{mex}([2,2,1])=0$$$ because $$$0$$$ does not belong to the array, and $$$\operatorname{mex}([0,3,1,2])=4$$$ because $$$0$$$, $$$1$$$, $$$2$$$, and $$$3$$$ appear in the array, but $$$4$$$ does not.

$$$^{\text{†}}$$$$$$u \bmod v$$$ denotes the remainder from dividing $$$u$$$ by $$$v$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the array $$$a$$$.

The second line of each testcase contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^6$$$) — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$. It is guaranteed that the sum of $$$\max(a_1,a_2,\ldots,a_n)$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each testcase, output $$$n$$$ integers — where the $$$i$$$-th integer represents the value of $$$f([a_1, a_2, \ldots, a_i])$$$.

Note

Consider the first testcase,

$$$a^{(1)} = [0]$$$, choosing $$$b = [1]$$$ gives $$$\operatorname{mex} = 1$$$.
$$$a^{(2)} = [0, 1]$$$, choosing $$$b = [1, 2]$$$ gives $$$\operatorname{mex} = 2$$$.
$$$a^{(3)} = [0, 1, 2]$$$, choosing $$$b = [1, 2, 3]$$$ gives $$$\operatorname{mex} = 3$$$.
$$$a^{(4)} = [0, 1, 2, 3]$$$, choosing $$$b = [1, 2, 3, 4]$$$ gives $$$\operatorname{mex} = 4$$$.

Consider the second testcase,

$$$a^{(1)} = [6]$$$, choosing $$$b = [6]$$$ gives $$$\operatorname{mex} = 1$$$.
$$$a^{(2)} = [6, 7]$$$, choosing $$$b = [3, 3]$$$ gives $$$\operatorname{mex} = 2$$$.

Mental Monumental (Hard Version)

Examples