Split

给出长度为 $n$ 的序列 $\{a\}$，求长度为 $2n$ 的正整数序列 $\{b\}$ 满足： - $\forall i\in[1,n],b_{2i-1}+b_{2i}=a_i$； - 满足上述条件基础上，将 $b$ 中值相同的段缩成一个数，要求 $b$ 的长度尽可能小。 求这个最小长度。 多组测试数据，保证 $\sum n\le 5\times 10^5$。

One day, BThero decided to play around with arrays and came up with the following problem: You are given an array $ a $ , which consists of $ n $ positive integers. The array is numerated $ 1 $ through $ n $ . You execute the following procedure exactly once: - You create a new array $ b $ which consists of $ 2n $ positive integers, where for each $ 1 \le i \le n $ the condition $ b_{2i-1}+b_{2i} = a_i $ holds. For example, for the array $ a = [6, 8, 2] $ you can create $ b = [2, 4, 4, 4, 1, 1] $ . - You merge consecutive equal numbers in $ b $ . For example, $ b = [2, 4, 4, 4, 1, 1] $ becomes $ b = [2, 4, 1] $ . Find and print the minimum possible value of $ |b| $ (size of $ b $ ) which can be achieved at the end of the procedure. It can be shown that under the given constraints there is at least one way to construct $ b $ .

The first line of the input file contains a single integer $ T $ ( $ 1 \le T \le 5 \cdot 10^5 $ ) denoting the number of test cases. The description of $ T $ test cases follows. The first line of each test contains a single integer $ n $ ( $ 1 \le n \le 5 \cdot 10^5 $ ). The second line contains $ n $ space-separated integers $ a_1 $ , $ a_2 $ , ..., $ a_n $ ( $ 2 \le a_i \le 10^9 $ ). It is guaranteed that $ \sum{n} $ over all test cases does not exceed $ 5 \cdot 10^5 $ .

For each test case, print a single line containing one integer — the minimum possible value of $ |b| $ .

3
3
6 8 2
1
4
3
5 6 6

3
1
2