#include <iostream>
#include <vector>
#include <stack>
#include <numeric>
#include <algorithm>
#include <map>

using namespace std;

#define rep(i,a,b) for ( int i = a ; i < (b) ; ++ i ) 
#define all(x) begin ( x ), end( x )
#define sz(x) (int)(x).size ( )
typedef long long ll ;
typedef pair < int , int > pii ;
typedef vector < int > vi;

struct SuffixArray {
    vi sa , lcp ;
    SuffixArray ( basic_string < int > &s , int lim = 256 ) {
        int n = sz ( s ) + 1 , k = 0 , a , b ;
        vi x ( all ( s ) + 1 ) , y ( n ) , ws ( max ( n , lim ) ) , rank ( n ) ;
        sa = lcp = y , iota ( all ( sa ) , 0 ) ;
        for ( int j = 0 , p = 0 ; p < n ; j = max ( 1 , j * 2 ) , lim = p ) {
            p = j , iota ( all ( y ) , n - j ) ;
            rep ( i , 0 , n ) if ( sa[ i ] >= j ) y[ p ++ ] = sa[ i ] - j ;
            fill ( all ( ws ) , 0 ) ;
            rep ( i , 0 , n ) ws[ x[ i ] ] ++ ; 
            rep ( i , 1 , lim ) ws[ i ] += ws[ i - 1 ] ; 
            for ( int i = n ; i -- ; ) { sa[ --ws[x[y[i]]]] = y[i] ; }
            swap ( x , y ) , p = 1 , x[ sa[ 0 ] ] = 0 ;
            rep ( i , 1 , n ) a = sa[ i - 1 ] , b = sa[ i ] , x[ b ] = 
                (y[a] == y[b] && y[ a + j ] == y[ b + j ] ) ? p - 1 : p ++ ;
        }
        rep ( i , 1 , n ) rank[ sa[ i ] ] = i ; 
        for ( int i = 0 , j ; i < n - 1 ; lcp[ rank[i++]] = k ) 
            for ( k && k-- , j = sa[rank[i]-1] ;
                s[i+k] == s[j+k] ; k++ );
    }
};

const int MAXN = 2e5 + 7 ;

int n ;
int a[ MAXN ] ;
int len[ MAXN ] ;
int pos[ MAXN ] , act[ MAXN ] , lcpval[ MAXN ] ;

class Tree {
    public :
    int tr[ 4 * MAXN ] ;
    void init ( int w , int l , int r ) {
        if ( l == r ) {
            tr[ w ] = lcpval[ l ] ;
            return ;
        }
        int mid = ( l + r ) / 2 ;
        init ( 2 * w , l , mid ) ;
        init ( 2 * w + 1 , mid + 1 , r ) ;
        tr[ w ] = min ( tr[ 2 * w ] , tr[ 2 * w + 1 ] ) ;
    }
    int query ( int w , int l , int r , int st , int en ) {
        if ( l > r || st > en ) { return MAXN ; }
        if ( r < st || en < l ) { return MAXN ; }
        if ( st <= l && r <= en ) { return tr[ w ] ; }
        int mid = ( l + r ) / 2 ;
        return min ( query ( 2 * w , l , mid , st , en ) , query ( 2 * w + 1 , mid + 1 , r , st , en ) ) ;
    }
};
Tree w ;

int get_lcp ( int x , int y ) {
    if ( x < 0 || n < x ) { return 0 ; }
    if ( y < 0 || n < y ) { return 0 ; }
    int l = pos[ x ] , r = pos[ y ] ;
    if ( l > r ) { swap ( l , r ) ; }
    ++ l ;
    // cout << x << " " << y << " -- " << l << " " << r << "\n" ;
    return w.query ( 1 , 1 , n , l , r ) ;
}

vector < int > en[ MAXN ] , first_bad[ MAXN ] ;
vector < int > by_len[ MAXN ] ;
vector < int > p2[ MAXN ] ;

ll ans[ MAXN ] ;

void solve(){
    cin >> n ;
    basic_string < int > s ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ] ;
        s += a[ i ] ;
    }
    SuffixArray aux ( s , n + 1 ) ;
    /**
    for ( int i = 0 ; i <= n ; ++ i ) {
        cout << aux.sa[ i ] << " " ;
    }
    cout << "\n" ;
    for ( int i = 0 ; i <= n ; ++ i ) {
        cout << aux.lcp[ i ] << " " ;
    }
    cout << "\n" ;
    **/
    for ( int i = 1 ; i <= n ; ++ i ) {
        pos[ aux.sa[ i ] + 1 ] = i ;
        act[ i ] = aux.sa[ i ] + 1 ;
        lcpval[ i ] = aux.lcp[ i ] ;
    }
    w.init ( 1 , 1  , n ) ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        len[ i ] = get_lcp ( 1 , i ) ;
        // cout << len[ i ] << " " ;
    }
    // cout << "\n" ;

    for ( int i = 0 ; i <= n + 4 ; ++ i ) {
        en[ i ].clear ( ) ;
        first_bad[ i ].clear ( ) ;
        by_len[ i ].clear ( ) ;
        p2[ i ].clear ( ) ;
    }

    ll right_large = n - 1 , right_small_sum = 0 ;
    for ( int i = 2 ; i <= n ; ++ i ) {
        first_bad[ len[ i ] + 1 ].push_back ( i ) ;
        by_len[ len[ i ] ].push_back ( i ) ;
        en[ i + len[ i ] ].push_back ( i ) ;
        p2[ i + len[ i ] + 1 ].push_back ( i ) ;
        if ( len[ i ] == 0 ) { -- right_large ; }
    }
    ll left_small_sum = 0 , left_large_cnt = 0 , left_large_sm = 0 ;
    ll left_large = 0 ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        if ( i > 1 ) {
            ++ left_large_cnt ;
            left_large_sm += i ;
        }
        for ( auto foo : en[ i ] ) {
            left_large_sm -= i ;
            -- left_large_cnt ;
        }
        for ( auto foo : p2[ i ] ) {
            left_small_sum += len[ foo ] ;
        }
        ll add = 0 ;
        map < int , ll > hh ;
        for ( auto x : first_bad[ i ] ) {
            if ( x > i ) {
                // add += i ;
                if ( x + i - 1 <= n ) { 
                    int aux = get_lcp ( i + 1 , x + i ) ;
                    hh[ a[ x + i - 1 ] ] += aux + 1 ;
                }
            }
        }
        for ( auto x : by_len[ i - 1 ] ) {
            -- right_large ;
            right_small_sum += i ;
        }
        if ( len[ i ] >= i ) { right_large -- ; }
        else { right_small_sum -= len[ i ] ; }

        ll mx = 0 ;
        for ( auto [ val1 , val2 ] : hh ) { mx = max ( mx , val2 ) ; }
        if ( i == 1 ) {
            cout << mx << " " << left_small_sum << " " << left_large_cnt * i - left_large_sm << "\n" ;
            cout << right_small_sum + right_large * ( i - 1 ) << "\n" ;
        }
        ans[ i ] = mx + left_small_sum + left_large_cnt * i - left_large_sm + right_small_sum + right_large * ( i - 1 ) ;
    }
    ll ret = 0 ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        ans[ i ] += n ;
        cout << ans[ i ] << " " ;
        ret = ( ret + ( ans[ i ] ^ i ) ) ;
    }
    cout << "\n" ;  
    cout << ret << "\n" ;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    while(t--){
        solve();
    }
}