#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + , mod = 1e9 + ;

int n;

int l[N], r[N], st[N];

ll a[N], sum[N][];

void up(ll &x, const ll &t)

{

    x = ((x + t) % mod + mod) % mod;

}

int main()

{

    int T;

    scanf("%d", &T);

    while(T--)

    {

        int top = ;

        ll ans = , tot = ;

        scanf("%d", &n);

        for(int i = ; i <= n; ++i)

        {

            scanf("%lld", &a[i]);

            tot = tot ^ a[i];

            for(int j = ; j < ; ++j) sum[i][j] = sum[i - ][j] + ((tot & ( << j)) > );

        }

        for(int i = ; i <= n; ++i)

        {

            l[i] = r[i] = i;

            while(top && a[i] > a[st[top]])

            {

                r[st[top - ]] = r[st[top]];

                l[i] = l[st[top]];

                --top;

            }

            st[++top] = i;

        }

        while(top) r[st[top - ]] = r[st[top]], --top;

        for(int i = ; i <= n; ++i)

        {

            ll pw = ;

            for(int j = ; j < ; ++j)

            {

                ll tmp1 = sum[r[i]][j] - sum[i - ][j], tmp2 = sum[i - ][j] - sum[max(l[i] - , )][j];

                up(ans, tmp1 * (ll)(i - l[i] +  - tmp2) % mod * pw % mod * a[i] % mod);

                up(ans, (ll)(r[i] - i +  - tmp1) * tmp2 % mod * pw % mod * a[i] % mod);

                pw = pw *  % mod;

            }

        }

        printf("%lld\n", ans);

    }

    return ;

}