暂无测试数据。

Description

\(\text{Scarral}\) 在玩祖玛游戏，他心血来潮想根据游戏规则出一个题。

给一个序列 \(a_1,a_2\cdots,a_n\)，你每次可以选择相同且相邻的三个数删除他们，如果序列中存在这样相同且相邻的三个数，\(\text{Scarral}\) 将不断将他们删除，\(\text{Scarral}\) 想知道最后序列中还剩几个数呢？

Input

第一行一个正整数 \(T\)（\(1\leq T\leq 10\)）表示数据组数。

对于每组数据，第一行一个正整数 \(n\) 表示序列长度，第二行 \(n\) 个正整数表示 \(a_1\)~\(a_n\)。

Output

对于每组数据输出一行，表示答案。

Sample

Sample input

2
7
1 1 1 2 2 2 3
8
1 2 2 2 1 1 3 2

Sample output

1
2

Hint

对于 \(30\%\) 的数据，\(3\leq n\leq 10\)，\(1\leq a_i\leq 10\)；
对于 \(60\%\) 的数据，\(3\leq n\leq 1000\)，\(1\leq a_i\leq 1000\)；
对于 \(100\%\) 的数据，\(3\leq n\leq 10^6\)，\(1\leq a_i\leq 10^9\)，\(\sum n\leq 10^6\)。