You are given a rectangular parallelepiped with sides of positive integer lengths A, B and C. 

Find the number of different groups of three integers (a, b, c) such that 1≤ a≤ b≤ c and parallelepiped A× B× C can be paved with parallelepipeds a× b× c. Note, that all small parallelepipeds have to be rotated in the same direction.

For example, parallelepiped 1× 5× 6 can be divided into parallelepipeds 1× 3× 5, but can not be divided into parallelepipeds 1× 2× 3.

Input

The first line contains a single integer t (1 ≤ t ≤ 10^5) — the number of test cases.

Each of the next t lines contains three integers A, B and C (1 ≤ A, B, C ≤ 10^5) — the sizes of the parallelepiped.

Output

For each test case, print the number of different groups of three points that satisfy all given conditions.

Example

Input

4
1 1 1
1 6 1
2 2 2
100 100 100


Output

1
4
4
165

Note

In the first test case, rectangular parallelepiped (1, 1, 1) can be only divided into rectangular parallelepiped with sizes (1, 1, 1).

In the second test case, rectangular parallelepiped (1, 6, 1) can be divided into rectangular parallelepipeds with sizes (1, 1, 1), (1, 1, 2), (1, 1, 3) and (1, 1, 6).

In the third test case, rectangular parallelepiped (2, 2, 2) can be divided into rectangular parallelepipeds with sizes (1, 1, 1), (1, 1, 2), (1, 2, 2) and (2, 2, 2). 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename F, typename S>
using ordered_map = tree<F, S, less<F>, rb_tree_tag, tree_order_statistics_node_update>;

//#define PB push_back
#define PB emplace_back
#define F first
#define S second
#define MP make_pair
#define endl '\n'
#define pf printf
#define sf scanf
#define left __left
#define right __right
#define tree __tree

const double PI = acos(-1);
const double eps = 1e-9;
const int inf = 2000000000;
const ll infLL = 9000000000000000000;
#define MOD 1000000007
//#define harmonic(n) 0.57721566490153286l+log(n)

#define mem(a,b) memset(a, b, sizeof(a) )
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define sqr(a) ((a) * (a))

#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fraction() cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed,ios::floatfield);

typedef vector<int>::iterator vit;
typedef set<int>::iterator sit;

inline bool checkBit(ll n, int i) { return n&(1LL<<i); }
inline ll setBit(ll n, int i) { return n|(1LL<<i);; }
inline ll resetBit(ll n, int i) { return n&(~(1LL<<i)); }

int dx[] = {0, 0, +1, -1};
int dy[] = {+1, -1, 0, 0};
//int dx[] = {+1, 0, -1, 0, +1, +1, -1, -1};
//int dy[] = {0, +1, 0, -1, +1, -1, +1, -1};

inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
inline bool isLeapYear(ll year) { return (year%400==0) || (year%4==0 && year%100!=0); }
inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline ll modInverse(ll a) { return modPow(a, MOD-2); }
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }

/*
bool seive[1010000];
vi prime;

void seiveGen(int limit) {
    limit += 100;
    int sqrtn = sqrt(limit);
    for(int i = 3; i <= sqrtn; i += 2) {
            if(!seive[i>>1]) {
                    for(int j = i * i; j < limit; j += i + i) {
                            seive[j>>1] = 1;
                    }
            }
    }
    prime.PB(2);
    for(int i = 3; i < limit; i += 2) {
            if(!seive[i>>1]) prime.PB(i);
    }
}
*/

//
//debug
#ifdef yamin
template < typename F, typename S >
ostream& operator << ( ostream& os, const pair< F, S > & p ) {
            return os << "(" << p.first << ", " << p.second << ")";
}

template < typename T >
ostream &operator << ( ostream & os, const vector< T > &v ) {
            os << "{";
                for(auto it = v.begin(); it != v.end(); ++it) {
                                if( it != v.begin() ) os << ", ";
                                        os << *it;
                                            }
                    return os << "}";
}

template < typename T >
ostream &operator << ( ostream & os, const set< T > &v ) {
            os << "[";
                for(auto it = v.begin(); it != v.end(); ++it) {
                                if( it != v.begin() ) os << ", ";
                                        os << *it;
                                            }
                    return os << "]";
}

template < typename T >
ostream &operator << ( ostream & os, const multiset< T > &v ) {
            os << "[";
                for(auto it = v.begin(); it != v.end(); ++it) {
                                if( it != v.begin() ) os << ", ";
                                        os << *it;
                                            }
                    return os << "]";
}

template < typename F, typename S >
ostream &operator << ( ostream & os, const map< F, S > &v ) {
            os << "[";
                for(auto it = v.begin(); it != v.end(); ++it) {
                                if( it != v.begin() ) os << ", ";
                                        os << it -> first << " = " << it -> second ;
                                            }
                    return os << "]";
}

#define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0)

clock_t tStart = clock();
#define timeStamp dbg("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC)

void faltu () {
            cerr << endl;
}

template <typename T>
void faltu( T a[], int n ) {
            for(int i = 0; i < n; ++i) cerr << a[i] << ' ';
                cerr << endl;
}

template <typename T, typename ... hello>
void faltu( T arg, const hello &... rest) {
            cerr << arg << ' ';
                faltu(rest...);
}
#else
#define dbg(args...)
#endif // yamin

const int N = 1e5 + 100;

map<int, bool> yo[N];
vi store[N];

ll func(int num, int bro) {
	if (bro == 0)
		return 1;
	if (bro == 1)
		return num;
	if (bro == 2)
		return (1LL * (num) * (num + 1)) / 2LL;
	ll ret = 0;
	for (int i = num; i > 0; --i) {
		ret += (1LL * i * (i + 1)) / 2LL;
	}
	dbg(num, bro, ret);
	return ret;
}

int main() {
	optimize();

	#ifdef yamin
	freopen("input.txt", "r", stdin);
	#endif

	for (int i = 1; i < N; ++i) {
		for (int j = 1; 1LL * j * j <= i; ++j) {
			if (i % j == 0) {
				store[i].PB(j);
				yo[i][j] = true;
				if (i / j != j) {
					store[i].PB(i / j);
					yo[i][i / j] = true;
				}
			}
		}
		sort(store[i].begin(), store[i].end());
	}

	int tc;
	cin >> tc;

	while (tc--) {
		int a, b, c;
		cin >> a >> b >> c;

		vi tstore;

		for (int i = 0; i < store[a].size(); ++i)
			tstore.PB(store[a][i]);
		for (int i = 0; i < store[b].size(); ++i)
			tstore.PB(store[b][i]);
		for (int i = 0; i < store[c].size(); ++i)
			tstore.PB(store[c][i]);
		sort(tstore.begin(), tstore.end());
		tstore.erase(unique(tstore.begin(), tstore.end()), tstore.end());
		int cnt[8] = {0};
		for (auto it : tstore) {
			int mask = 0;
			if (yo[a][it])
				mask = setBit(mask, 0);
			if (yo[b][it])
				mask = setBit(mask, 1);
			if (yo[c][it])
				mask = setBit(mask, 2);
			++cnt[mask];
		}
		dbg(tstore);
		dbg(cnt, 8);
		ll ans = 0LL;
		/*
		for (int i = 1; i < 8; ++i) {
			for (int j = i + 1; j < 8; ++j) {
				for (int k = j + 1; k < 8; ++k) {
					int ci = __builtin_popcount(i), cj = __builtin_popcount(j), ck = __builtin_popcount(k);
					for (int x = 0; x <= ci; ++x) {
						for (int y = 0; y <= cj; ++y) {
							for (int z = 0; z <= ck; ++z) {
								if (x + y + z != 3)
									continue;
								int tmask = ((x > 0) * i) | ((y > 0) * j) | ((z > 0) * k);
								if (tmask != 7)
									continue;
								ans += func(cnt[i], x) * func(cnt[j], y) * func(cnt[k], z);
							}
						}
					}
				}
			}
		}
		*/
		for (int i = 1; i < 8; ++i) {
			for (int j = i; j < 8; ++j) {
				for (int k = j; k < 8; ++k) {
					int tmask = i;
					tmask |= j;
					tmask |= k;
					if (tmask != 7)
						continue;
					map<int, int> exist;
					exist[i]++;
					exist[j]++;
					if (exist[i] > __builtin_popcount(i))
						continue;
					if (exist[j] > __builtin_popcount(j))
						continue;
					if (exist[k] > __builtin_popcount(k))
						continue;
					if (exist.size() == 1) {
						auto it = exist.begin();
						ans += func(cnt[it->F], 3);
					}
					else if (exist.size() == 2) {
						auto it = exist.begin();
						auto it2 = it; ++it2;
						ans += func(cnt[it->F], it->S) * func(cnt[it2->F], it2->S);
					}
					else if (exist.size() == 3) {
						auto it = exist.begin();
						auto it2 = it; ++it2;
						auto it3 = it2; ++it3;
						ans += func(cnt[it->F], 1) * func(cnt[it2->F], 1) * func(cnt[it3->F], 1);
					}
				}
			}
		}
		cout << ans << endl;
	}

	return 0;
}