#include<bits/stdc++.h>

#define ff first
#define ss second

#define typet typename T
#define typeu typename U
#define types typename... Ts
#define tempt template < typet >
#define tempu template < typeu >
#define temps template < types >
#define final constexpr const

tempt struct range {
	T b, e;
	range (T b, T e): b(b), e(e) {}
	T begin() const {return b;}
	T end() const {return e;}
};
tempt range<T> make_range(T b, T e) {return range <T> (b, e);}

tempt struct is_cont {
	static final bool value = false;
};
tempt struct is_cont<range<T>>{
	static final bool value = true;
};
temps struct is_cont<std::vector<Ts...>>{
	static final bool value = true;
};
temps struct is_cont<std::set<Ts...>>{
	static final bool value = true;
};
temps struct is_cont<std::map<Ts...>>{
	static final bool value = true;
};
template < typet, typeu > std::ostream &
operator << (std::ostream &os, const std::pair<T, U> &p) {
	return os << '<' << p.ff << ',' << p.ss << '>';
}
tempt std::enable_if_t<is_cont<T>::value, std::ostream> &
operator << (std::ostream &os, const T &c) {
	auto it = c.begin();
	if (it == c.end()) return os << "{}";
	for (os << '{' << *it; ++it != c.end(); os << ',' << *it);
	return os << '}';
}
void dbg() {std::cerr << std::endl;}
template < typet, types > void dbg(T arg, Ts... args) {
	std::cerr << ' ' << arg; dbg(args...);
}
#ifndef ONLINE_JUDGE
#define debug(arg...) do {std::cerr << "["#arg"] :"; dbg(arg);} while (false)
#else
#define debug(...) do {} while (false)
#endif

using i64 = long long;
using pii = std::pair<int, int>;
using vi = std::vector<int>;
using vp = std::vector<pii>;

#define lowbit(x) ((x) & (-x))
#define all(x) x.begin(), x.end()
#define set_all(x, y) std::memset(x, y, sizeof(x))
#define set_n(x, y, n) std::memset(x, y, sizeof(decltype(*(x))) * (n))

tempt void Min(T &x, const T &y) {if (x > y) x = y;}
tempt void Max(T &x, const T &y) {if (x < y) x = y;}

final int mod = 998244353;
inline int add(int x, int y) { return x + y < mod ? x + y : x + y - mod; }
inline int sub(int x, int y) { return x < y ? mod + x - y : x - y; }
inline int mul(i64 x, int y) { return x * y % mod; }
inline void Add(int& x, int y) { x = add(x, y); }
inline void Sub(int& x, int y) { x = sub(x, y); }
inline void Mul(int& x, int y) { x = mul(x, y); }
int pow(int x, int y) {
	int z = 1;
	for (; y; y /= 2) {
		if (y & 1) Mul(z, x);
		Mul(x, x);
	}
	return z;
}

void solve() {
	std::queue<std::string> que;
	std::string st = "00000000";
	que.emplace(st);
	int cnt = 0;
	std::unordered_map<std::string, int> mp;
	for (int i = 0; i < 729; i++) {
		int now = i, cur = 0;
		std::string temp = st;
		while (now) {
			int p = now % 3;
			now /= 3;
			while (p--) {
				temp[cur] += 1;
				temp[cur + 1] += 1;
				temp[cur + 2] += 1;
			}
			++cur;
		}
		//debug(temp);
		mp[temp] = cnt++;
	}
	int n;
	std::cin >> n;
	vi A(n + 1);
	for (int i = 1; i <= n; i++) {
		std::cin >> A[i];
	}
	std::string now = "00000000";
	std::unordered_map<std::string, int> Idx_Map;
	cnt = 0;
	for (int i = 0; i < 6561; i++) {
		std::string str;
		int now = i;
		while (now) {
			str += char('0' + now % 3);
			now /= 3;
		}
		std::reverse(all(str));
		while (str.size() < 8) {
			str = "0" + str;
		}
		Idx_Map[str] = cnt++;
	}
	std::queue<std::vector<int> > Table[6561];
	std::vector<int> Have(8, 0);
	int Idx[6561] = {0};
	Table[0].emplace(Have);
	i64 ans = 0;
	for (int i = 1; i <= n; i++) {
		--A[i];
		int c = now[A[i]] - '0';
		c = (c + 1) % 3;
		now[A[i]] = char(c + '0');
		Have[A[i]]++;
		for (auto [x, y] : mp) {
			std::string temp;
			int nxt = 0;
			for (int j = 0; j < 8; j++) {
				int p = x[j] - '0', q = now[j] - '0';
				if (p > Have[j]) {
					nxt = 1;
					break;
				}
				p %= 3, q %= 3;
				p = (q - p + 3) % 3;
				temp += char(p + '0');
			}
			if (nxt) {
				continue;
			}
			int id = Idx_Map[temp];
			while (!Table[id].empty()) {
				auto str = Table[id].front();
				bool ok = 1;
				if (ok) {
					Idx[id]++;
					Table[id].pop();
				} else {
					break;
				}
			}
			if (Idx[id] > 0) {
				//debug(i, now, x, temp, Idx[id]);
			}
			ans += Idx[id];
		}
		Table[Idx_Map[now]].emplace(Have);

	}
	//debug("Ans:");
	std::cout << ans << '\n';
}
// vector[]  



int main() {
	std::cin.tie(nullptr) -> sync_with_stdio(false);
    std::cout.tie(nullptr);
	int T = 1;
	std::cin >> T;
	for (int cas = 1; cas <= T; cas++) {
		solve();
	}
	return 0;
}
/*
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
*/