#include <stdio.h>

int main(void) {
		int n, x, **z, m, i, j, q, p, sum;
	float y;

	scanf("%d", &x);
	for (i = 0; i < x; i++)
	{
		sum = 0;
		scanf("%d", &n);
		z = (int**)malloc(sizeof(int*)*n);
		for (j = 0; j < n; j++)
			z[j] = (int*)malloc(sizeof(int)*n);
		for (p = 0; p < n; p++)
			for (q = 0; q < n; q++)
			{
				scanf("%d", &z[p][q]);
				m = sqrt(z[p][q]);
				y = sqrt(z[p][q]) - m;
				if ((y) == 0)
					sum += z[p][q];
			}
		printf("%d\n", sum);
		for (j = 0; j < n; j++)
			free(z[j]);
		free(z);
	}
	
	return 0;
}