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). 
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.NoSuchElementException;

public class Main {
	class FastScanner {
		private final InputStream in = System.in;
		private final byte[] buffer = new byte[1024];
		private int ptr = 0;
		private int buflen = 0;

		private boolean hasNextByte() {
			if (ptr < buflen) {
				return true;
			} else {
				ptr = 0;
				try {
					buflen = in.read(buffer);
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (buflen <= 0) {
					return false;
				}
			}
			return true;
		}

		private int readByte() {
			if (hasNextByte())
				return buffer[ptr++];
			else
				return -1;
		}

		private boolean isPrintableChar(int c) {
			return 33 <= c && c <= 126;
		}

		public boolean hasNext() {
			while (hasNextByte() && !isPrintableChar(buffer[ptr]))
				ptr++;
			return hasNextByte();
		}

		public String next() {
			if (!hasNext())
				throw new NoSuchElementException();
			StringBuilder sb = new StringBuilder();
			int b = readByte();
			while (isPrintableChar(b)) {
				sb.appendCodePoint(b);
				b = readByte();
			}
			return sb.toString();
		}

		public long nextLong() {
			if (!hasNext())
				throw new NoSuchElementException();
			long n = 0;
			boolean minus = false;
			int b = readByte();
			if (b == '-') {
				minus = true;
				b = readByte();
			}
			if (b < '0' || '9' < b) {
				throw new NumberFormatException();
			}
			while (true) {
				if ('0' <= b && b <= '9') {
					n *= 10;
					n += b - '0';
				} else if (b == -1 || !isPrintableChar(b)) {
					return minus ? -n : n;
				} else {
					throw new NumberFormatException();
				}
				b = readByte();
			}
		}

		public int nextInt() {
			long nl = nextLong();
			if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
				throw new NumberFormatException();
			return (int) nl;
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

	}

	public static void main(String[] args) {
		new Main().run();
	}

	ArrayList<Integer>[] div;

	void run() {
		div = new ArrayList[100001];
		for (int i = 1; i < div.length; ++i) {
			div[i] = new ArrayList<>();
		}
		for (int i = 1; i < div.length; ++i) {
			for (int j = i; j < div.length; j += i) {
				div[j].add(i);
			}
		}
		FastScanner sc = new FastScanner();
		PrintWriter pw = new PrintWriter(System.out);
		int T = sc.nextInt();
		for (int t = 0; t < T; ++t) {
			int A = sc.nextInt();
			int B = sc.nextInt();
			int C = sc.nextInt();
			long da = div[A].size();
			long db = div[B].size();
			long dc = div[C].size();
			long dab = div[(int) gcd(A, B)].size();
			long dbc = div[(int) gcd(B, C)].size();
			long dac = div[(int) gcd(C, A)].size();
			long dabc = div[(int) gcd(A, B, C)].size();
			long oa = da - dab - dac + dabc;
			long ob = db - dab - dbc + dabc;
			long oc = dc - dac - dbc + dabc;
			long ans = 0;
			// (100)(010)(001)
			ans += oa * ob * oc;
			// (100)(010)(111)
			ans += oa * ob * dabc;
			ans += ob * oc * dabc;
			ans += oa * oc * dabc;
			// (100)(010)(011)
			ans += oa * ob * (dbc - dabc);
			ans += oa * ob * (dac - dabc);
			ans += ob * oc * (dac - dabc);
			ans += ob * oc * (dab - dabc);
			ans += oa * oc * (dbc - dabc);
			ans += oa * oc * (dab - dabc);
			// (100)(011)(011)
			ans += oa * (dbc - dabc);
			ans += ob * (dac - dabc);
			ans += oc * (dab - dabc);
			ans += oa * (dbc - dabc) * (dbc - dabc - 1) / 2;
			ans += ob * (dac - dabc) * (dac - dabc - 1) / 2;
			ans += oc * (dab - dabc) * (dab - dabc - 1) / 2;
			// (100)(011)(101)
			ans += oa * (dbc - dabc) * (dac - dabc + dab - dabc);
			ans += ob * (dac - dabc) * (dab - dabc + dbc - dabc);
			ans += oc * (dab - dabc) * (dac - dabc + dbc - dabc);
			// (100)(110)(101)
			ans += oa * (dab - dabc) * (dac - dabc);
			ans += ob * (dab - dabc) * (dbc - dabc);
			ans += oc * (dac - dabc) * (dbc - dabc);
			// (100)(011)(111)
			ans += oa * (dbc - dabc) * dabc;
			ans += ob * (dac - dabc) * dabc;
			ans += oc * (dab - dabc) * dabc;
			// (100)(110)(111)
			ans += oa * dabc * (dab - dabc);
			ans += oa * dabc * (dac - dabc);
			ans += ob * dabc * (dab - dabc);
			ans += ob * dabc * (dbc - dabc);
			ans += oc * dabc * (dac - dabc);
			ans += oc * dabc * (dbc - dabc);
			// (100)(111)(111)
			ans += oa * dabc + oa * dabc * (dabc - 1) / 2;
			ans += ob * dabc + ob * dabc * (dabc - 1) / 2;
			ans += oc * dabc + oc * dabc * (dabc - 1) / 2;
			// (110)(011)(101)
			ans += (dab - dabc) * (dbc - dabc) * (dac - dabc);
			// (110)(110)(011)
			ans += ((dab - dabc) + (dab - dabc) * (dab - dabc - 1) / 2) * (dac - dabc + dbc - dabc);
			ans += ((dbc - dabc) + (dbc - dabc) * (dbc - dabc - 1) / 2) * (dab - dabc + dac - dabc);
			ans += ((dac - dabc) + (dac - dabc) * (dac - dabc - 1) / 2) * (dbc - dabc + dab - dabc);
			// (110)(110)(111)
			ans += ((dab - dabc) + (dab - dabc) * ((dab - dabc) - 1) / 2) * dabc;
			ans += ((dac - dabc) + (dac - dabc) * (dac - dabc - 1) / 2) * dabc;
			ans += ((dbc - dabc) + (dbc - dabc) * (dbc - dabc - 1) / 2) * dabc;
			// (101)(011)(111)
			ans += (dac - dabc) * (dbc - dabc) * dabc;
			ans += (dab - dabc) * (dbc - dabc) * dabc;
			ans += (dac - dabc) * (dab - dabc) * dabc;
			// (110)(111)(111)
			ans += (dab - dabc) * (dabc + dabc * (dabc - 1) / 2);
			ans += (dac - dabc) * (dabc + dabc * (dabc - 1) / 2);
			ans += (dbc - dabc) * (dabc + dabc * (dabc - 1) / 2);
			// (111)(111)(111)
			ans += dabc + dabc * (dabc - 1) + dabc * (dabc - 1) * (dabc - 2) / 6;
			pw.println(ans);
		}
		pw.close();
	}

	long lcm(long a, long b) {
		return a / gcd(a, b) * b;
	}

	long gcd(long a, long b, long c) {
		return gcd(a, gcd(b, c));
	}

	long gcd(long a, long b) {
		if (b < a) {
			return gcd(b, a);
		}
		if (a == 0)
			return b;
		return gcd(b % a, a);
	}

	void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}