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$.