#include <bits/stdc++.h>
using ll = long long;
using std::cin;
using std::cout;
using std::vector;
using std::array;
using std::pair;
using std::ranges::min;
ll correct_sol(ll n, const vector<ll>& a) {
vector<array<ll, 60>> pref(n + 1);
for (ll i = 0; i < n; ++i) {
pref[i + 1] = pref[i];
for (ll b = 0; b < 60; ++b)
pref[i + 1][b] += (a[i] >> b) & 1;
}
ll ans = 0;
for (ll i = n - 1; i >= 0; --i) {
for (ll b = 0; i + (1 << b) - 1 < n; ++b) {
auto check = [&] (ll L, ll R) {
bool good = true;
for (ll b2 = b + 1; b2 < 60; ++b2) {
ll x = (a[i] >> b2) & 1;
ll y = pref[R][b2] - pref[L][b2];
if (x == 0) good &= y == 0;
else good &= y == (R - L);
}
return good;
};
ll L = i - 1 + (1 << b), R = min(n, L + (1 << b));
if (check(L, R)) {
ans += R - L;
continue;
}
ll lo = L - 1, hi = R - 1;
while (lo < hi) {
ll mid = (lo + hi) / 2;
if (check(lo, mid + 1))
lo = mid + 1;
else
hi = mid;
}
ans += hi - L;
break;
}
}
return ans;
}
ll my_sol(ll n, const vector<ll>& a) {
// bits[j].first stores whether the j'th bit of the last num was set
// bits[j].second stores how many contigous previous num had the same bits[j].first
vector<pair<ll, ll>> bits(60);
ll ans = 0;
for (ll i = n - 1; i >= 0; --i){
ll min_right = n;
for (ll j = 0; j < 60; ++j){
bool cur_bit = a[i] & (1ll << j);
if (cur_bit == bits[j].first)
++bits[j].second;
else
bits[j] = {cur_bit, 1};
if (bits[j].second < (1ll << j))
min_right = min(min_right, i + bits[j].second);
}
ans += min_right - i;
}
return ans;
}
static std::mt19937_64 RNG(std::chrono::high_resolution_clock::now().time_since_epoch().count());
int main(){
std::freopen("output.txt", "w", stdout);
ll t;
cin >> t;
while (t--){
ll n = RNG() % 200000 + 1;
vector<ll> a(n);
for (ll& x : a)
x = RNG() % (1ll << 60);
ll ans1 = correct_sol(n, a);
ll ans2 = my_sol(n, a);
if (ans1 != ans2){
cout << n << '\n';
for (ll& x : a)
cout << x << ' ';
cout << "\nCorrect: " << ans1 << "\nMine: " << ans2;
return 0;
}
}
}