코코의 노래

서울대학교에는 '코코'라는 특별한 앵무새가 살고 있다. 코코는 들려오는 소리의 수열을 듣고 그 중 일부를 독특한 방식으로 흉내내곤 한다.

코코는 다음과 같은 형태의 소리 수열을 흉내낼 수 있다.

• 코코의 흉내내기는 어떤 양의 정수 $k$를 먼저 외치는 것으로 시작한다. 즉 소리 수열의 첫 번째 원소는 $k$이다.
• 이어서, 길이가 짝수 $M$인 $k$개의 소리 수열 $S_1, S_2,\cdots,S_k$를 연속하여 외친다.
• 소리 수열 $S_i$의 앞쪽 절반의 수 $\frac{M}{2}$개를 떼어 만든 수열은 $S_1, S_2,\cdots, S_k$에서 모두 동일해야 한다. ($1\le i\le k$)
• 소리 수열 $S_i$의 뒤쪽 절반의 수 $\frac{M}{2}$개는 제멋대로 소리를 내서, 서로 달라도 상관이 없다.

서울대학교 관악캠퍼스 전체에 울려 퍼진 길이 $N$의 소리 수열 $A$가 주어졌을 때, $1 \le l < r \le N$을 만족하는 모든 연속 부분 수열 $[A_l,A_{l+1},\cdots, A_r]$ 중 코코가 흉내낼 수 있는 것의 개수를 구하자.

더 엄밀하게는, 어떤 양의 정수 $p$에 대해 연속 부분 수열의 길이가 $1+2A_s p$이며, 모든 $1 \le j < A_s$와 $1 \le l \le p$에 대해 $A_{s+l} = A_{s+l+j \cdot 2p}$를 만족하는 경우에만 코코가 시작 인덱스가 $s$인 연속 부분 수열을 흉내낼 수 있다.

첫 번째 줄에 테스트 케이스의 개수 $T(1 \le T \le 300\,000)$가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 소리 수열의 길이 $N(1 \le N\le 300\,000)$이 주어진다.

각 테스트 케이스의 두 번째 줄에는 $N$개의 정수로 이루어진 소리 수열 $A_1, A_2, \cdots, A_N(1 \le A_i \le 10^9)$이 공백으로 구분되어 주어진다.

모든 테스트 케이스에 대한 $N$의 총합은 $300\,000$을 넘지 않는다.

입력으로 주어지는 모든 수는 정수이다.

각 테스트 케이스마다, 코코가 흉내낼 수 있는 연속 부분 수열의 총 개수를 한 줄에 하나씩 출력한다.