如果一个正整数多重集 $s$ 满足 $s = \{x, x, x\}$，其中 $x$ 为某个正整数，则称其为“刻子”（Pong）。

如果一个正整数多重集 $s$ 满足 $s = \{x, x+1, x+2\}$，其中 $x$ 为某个正整数，则称其为“顺子”（Chow）。

如果一个正整数多重集可以被划分为若干个（可以为零个）“刻子”和若干个（可以为零个）“顺子”，则称其为“麻将”（Mahjong）。注意，此定义与现实中的麻将规则不同。

现在给定 $n$ 个整数 $a_1, a_2, \dots, a_n$。你的任务是计算满足多重集 $\{a_l, a_{l+1}, \dots, a_r\}$ 是“麻将”的区间 $[l, r]$（$1 \le l \le r \le n$）的数量。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试数据组数。

对于每组测试数据，第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示整数的个数。

接下来一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 8$)。

保证所有测试数据的 $n$ 之和不超过 $10^5$。

输出格式

对于每组测试数据，输出一个整数，表示答案。

样例

样例输入 1

5
4
1 1 1 1
6
1 2 3 1 2 3
7
6 5 8 7 6 3 2
8
1 2 1 2 1 2 1 3
9
2 2 4 4 1 1 1 3 3

样例输出 1

2
5
1
3
2