2077年,世界被机器人奴役后,机器人决定实施教育改革,现在取模运算只在《世界古代史》系教授。这是该学院的入学任务之一:
我们定义 美女 正整数数组 $$$b$$$ 作为所有对 $$$1 \leq i, j \leq n$$$ 的最大值 $$$f(b_i, b_j)$$$,其中 $$$f(x, y) = (x \bmod y) + (y \bmod x)$$$。
给定一个长度为 $$$n$$$ 的正整数数组 $$$a$$$,输出 $$$n$$$ 数字,其中第 $$$i$$$ 个数字 ($$$1 \leq i \leq n$$$) 是 数组 $$$a_1, a_2, \ldots, a_i$$$ 的 美女 。
$$$x \bmod y$$$ 是 $$$x$$$ 除以 $$$y$$$ 的余数。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — 数组 $$$a$$$ 的大小。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^6$$$。
输出
对于每个测试用例,输出 $$$n$$$ 个整数 — 数组 $$$a$$$ 的所有前缀的优点。
示例
输入复制
253 1 4 1 575 11 11 4 2 1 10
输出复制
0 1 4 4 5 0 6 6 7 7 7 11
注意
数组 $$$3$$$ 的美妙之处在于 $$$0$$$。
数组 $$$3, 1$$$ 的美妙之处在于 $$$f(3, 1) = 1$$$。
数组 $$$3, 1, 4$$$ 的美妙之处在于 $$$f(3, 4) = 4$$$。
数组 $$$3, 1, 4, 1$$$ 的美妙之处在于 $$$f(4, 3) = 4$$$。
数组 $$$3, 1, 4, 1, 5$$$ 的美妙之处在于 $$$f(4, 5) = 5$$$。