有一天,BThero 决定尝试一下数组,并提出了以下问题:
给定一个数组 $$$a$$$,它由 $$$n$$$ 正整数组成。该数组从 $$$1$$$ 到 $$$n$$$ 进行编号。您只需执行一次以下过程:
- 您创建一个新数组 $$$b$$$,其中包含 $$$2n$$$ 正整数,其中对于每个 $$$1 \le i \le n$$$,条件 $$$b_{2i-1}+b_{2i} = a_i$$$ 成立。例如,对于数组 $$$a = [6, 8, 2]$$$,您可以创建 $$$b = [2, 4, 4, 4, 1, 1]$$$。
- 您合并 $$$b$$$ 中连续的相等数字。例如,$$$b = [2, 4, 4, 4, 1, 1]$$$ 变为 $$$b = [2, 4, 1]$$$。
查找并打印在过程结束时可以达到的 $$$|b|$$$ 的最小可能值($$$b$$$ 的大小)。可以证明,在给定的约束下,至少有一种构造$$$b$$$的方法。
输入
输入文件的第一行包含一个整数 $$$T$$$ ($$$1 \le T \le 5 \cdot 10^5$$$) 表示测试用例的数量。 $$$T$$$ 测试用例的描述如下。
每个测试的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$)。
第二行包含 $$$n$$$ 空格分隔的整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$2 \le a_i \le 10^9$$$)。
保证所有测试用例的 $$$\sum{n}$$$ 不超过 $$$5 \cdot 10^5$$$。
输出
对于每个测试用例,打印一行包含一个整数 - $$$|b|$$$ 的最小可能值。
示例
输入 #1
3 3 6 8 2 1 4 3 5 6 6
输出 #1
3 1 2