"祂的泪是永不融化的冰，祂的背是坚不可摧的山岩，祂的呼吸是冬日的寒风，祂的笑是春日的暖阳。"

"如若一切都是Elo的馈赠，那么Elo的子民又何需畏惧风雪？ "

"Elo，请注视您的子民......"

"响铃之音来自祂最澄澈的心灵，爱祂的人无不垂首聆听，而Elo注视着所有虔诚的子民。"

Elo一直都在注视着他的子民，注视着这片土地上的正在发生的一切，

"今岁乃希瓦艾什年也"，Elo此般记录到，

谢拉格早已在这闭塞的群山之中走过了$n$年，每年，Elo都会选取谢拉格$m$个家族势力中最为强盛的家族，给这一年下一个定义。比如，今年就是"希瓦艾什年"，

Elo将这$n$年来的定义整理成一个长度为$n$正整数序列$A$，

在一段时期内，一个家族不可能总是保持在最强盛的状态。Elo认为，对于一段时期区间$[L,R]$，如果存在一个家族$x$，这个家族在这段时期中，有超过一半的年份均是最为强盛的家族（$x$在区间中出现次数超过一半），那么Elo就称这一段时期时"被统治的时期"，

Elo祂想知道，谢拉格这$n$年来，有多少个时期是"被统治的时期"。

第一行一个正整数$T$，表示数据组数；

接下来$T$组数据，对于每组数据，第一行一个正整数$n\ (1\leq n \leq 10^5)$，

第二行$n$个正整数，第i个正整数为$a_i\ (1\leq a_i \leq 10^6)$，表示序列$A$，

保证对于所有的数据，有$\sum n \leq 3*10^5$

输出$T$行，每行一个正整数，表示这一组数据中，有多少个时期是"被统治的时期"。