CF1864

const int modo = 998244353;
int a[200005];
long long ans = 0;
void dfs(int l,int r,int num_l,int num_r)
{
if (l == r)
{
return;
}
int num_mid = (num_l + num_r) >> 1;
if (num_mid == num_l)
{
ans += (r-l) * (r-l);
return;
}
int mid = lower_bound(a+l,a+r,num_mid) - a;
ans += (long long)(mid - l) * (r - mid) * 3;
dfs(l,mid,num_l,num_mid);
ans += (long long)(r - mid) * (r - mid);
dfs(mid,r,num_mid,num_r);
}
int power(int x,int y)
{
if (y == 0)
{
return 1;
}
int t = power(x,y/2);
t = (long long)t * t % modo;
if (y % 2 == 1)
{
t = (long long)t * x % modo;
}
return t;
}
int main()
{
#ifdef absi2011
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int t;
scanf("%d",&t);
int zu;
for (zu=0;zu<t;zu++)
{
ans = 0;
int n;
scanf("%d",&n);
int i;
for (i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
sort(a,a+n);
dfs(0,n,0,1<<30);
ans %= modo;
ans *= power(n, modo - 2);
ans %= modo;
ans *= power(n, modo - 2);
ans %= modo;
printf("%lld\n",ans);
}
return 0;
}

char a[3005][3005];
int tag[3005][3005][4];
int main()
{
#ifdef absi2011
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int t;
scanf("%d",&t);
int zu;
for (zu=0;zu<t;zu++)
{
int n;
scanf("%d",&n);
int i;
for (i=0;i<n;i++)
{
scanf("%s",a[i]);
}
for (i=0;i<n;i++)
{
int j;
for (j=0;j<n;j++)
{
int k;
for (k=0;k<4;k++)
{
tag[i][j][k] = 0;
}
}
}
int ans = 0;
for (i=0;i<n;i++)
{
int j;
for (j=0;j<n;j++)
{
int k;
int xors = 0;
for (k=0;k<4;k++)
{
xors ^= tag[i][j][k];
}
if ((a[i][j] ^ xors) == '1')
{
tag[i][j][3] ^= 1;
ans ++;
}
for (k=0;k<4;k++)
{
if (!tag[i][j][k])
{
continue;
}
if ((j != 0) && ((k & 1) != 0))
{
tag[i+1][j-1][k & 1] ^= 1;
}
tag[i+1][j][0] ^= 1;
if ((j != n-1) && ((k & 2) != 0))
{
tag[i+1][j+1][k & 2] ^= 1;
}
}
}
}
printf("%d\n",ans);
}
return 0;
}