#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <numeric>
#include <cassert>
#include <cmath>
#include <map>
#include <set>

using namespace std;
typedef long long LL;
typedef double LD;

#define FOR(k,a,b) for(int k(a); k < (b); ++k)
#define FORD(k,a,b) for(int k(b-1); k >= (a); --k)
#define REP(k,a) for(int k=0; k < (a); ++k)
#define ABS(a) ((a)>0?(a):-(a))
#define EPS 1e-9
#define INF 1e9

const LL MOD = 359999;
const int MM = 1e9 + 7;

int gcd(int a, int b)
{
	return b ? gcd(b, a%b) : a;
}

LL greedy(const vector<int>& y)
{
	LL res = 0;
	REP(i, y.size())
	{
		if ((i * 100) / y.size() != ((i - 1) * 100) / y.size())
		{
			fprintf(stderr, "%d%\n", (i * 100) / y.size());
		}
		REP(j, y.size())
		{
			int g = gcd(y[i], y[j]);
			if (g == 1)
			{
				res += y.size();
			}
			else
			{
				REP(k, y.size())
					if (gcd(y[k], g) == 1)
						++res;
			}
		}
	}
	return res;
}

int main(int argc, char** argv) {
#ifdef HOME
	freopen("in.txt", "rb", stdin);
	freopen("out.txt", "wb", stdout);
#endif
	int T,N;
	scanf("%d", &T);
	vector<int> p(MOD + 1), m(MOD+1);
	m[1] = 1;
	FOR(i, 2, MOD + 1)
	{
		if (!p[i])
		{
			int j = i;
			while (j < MOD + 1)
			{
				if (!p[j])
					p[j] = i;
				j += i;
			}
		}
		if (p[i / p[i]] == p[i])
			m[i] = 0;
		else
			m[i] = -1 * m[i /p[i]];
	}

	while (T--)
	{
		scanf("%d", &N);
		vector<int> X(N);
		vector<LL> Y(MOD + 1);
		LL res = 0, db;
		REP(i, N)
			scanf("%d", &X[i]);
		REP(i, N) REP(j, N)
		{
			LL y = X[i];
			y *= X[j];
			y %= MOD;
			Y[y]++;
		}
		//LL gres = greedy(debugy);
		res += 3 * Y[0] * Y[0] * Y[1];
		res %= MM;
		FOR(i, 1, MOD + 1)
		{
			if(!m[i]) continue;
			int j = i;
			db = 0;
			while (j < MOD + 1)
			{
				db += Y[j];
				j += i;
			}
			res += MM + (db * db * db)*m[i];
			//
			res += MM + 3*Y[0] * db * db*m[i];
			//
 			res %= MM;
		}

		printf("%lld\n", res);
	}
	return 0;
}