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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Set;
import java.io.IOException;
import java.util.HashMap;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.StringTokenizer;
import java.util.Map;
import java.io.BufferedReader;
import java.util.BitSet;
import java.util.Collections;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author bacali
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        DPaveTheParallelepiped solver = new DPaveTheParallelepiped();
        solver.solve(1, in, out);
        out.close();
    }

    static class DPaveTheParallelepiped {
        BitSet isPrime = new BitSet(100005);
        ArrayList<Integer> primes = new ArrayList<>();

        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            int n = in.nextInt();
            sieve();
            for (int i = 0; i < n; i++) {
                ArrayList<Integer>[] tab = new ArrayList[3];
                tab[0] = new ArrayList<>(divs(in.nextInt()));
                tab[1] = new ArrayList<>(divs(in.nextInt()));
                tab[2] = new ArrayList<>(divs(in.nextInt()));
                for (int j = 0; j < tab.length; j++) {
                    Collections.sort(tab[j]);
                }
                int ans = 0;
                for (int j = 0; j < tab[0].size(); j++) {
                    int a = tab[0].get(j);
                    int ind = upper_bound(tab[1], 0, tab[1].size() - 1, a);
                    for (int k = ind; k < tab[1].size(); k++) {
                        int b = tab[1].get(k);
                        int ind2 = upper_bound(tab[2], 0, tab[2].size() - 1, b);
                        ans += tab[2].size() - ind2;
                    }
                }
                int max = ans;
                ans = 0;
                for (int j = 0; j < tab[0].size(); j++) {
                    int a = tab[0].get(j);
                    int ind = upper_bound(tab[2], 0, tab[2].size() - 1, a);
                    for (int k = ind; k < tab[2].size(); k++) {
                        int b = tab[2].get(k);
                        int ind2 = upper_bound(tab[1], 0, tab[1].size() - 1, b);
                        ans += tab[1].size() - ind2;
                    }
                }
                max = Math.max(max, ans);

                ans = 0;
                for (int j = 0; j < tab[1].size(); j++) {
                    int a = tab[1].get(j);
                    int ind = upper_bound(tab[0], 0, tab[0].size() - 1, a);
                    for (int k = ind; k < tab[0].size(); k++) {
                        int b = tab[0].get(k);
                        int ind2 = upper_bound(tab[2], 0, tab[2].size() - 1, b);
                        ans += tab[2].size() - ind2;
                    }
                }
                max = Math.max(max, ans);

                ans = 0;
                for (int j = 0; j < tab[1].size(); j++) {
                    int a = tab[1].get(j);
                    int ind = upper_bound(tab[2], 0, tab[2].size() - 1, a);
                    for (int k = ind; k < tab[2].size(); k++) {
                        int b = tab[2].get(k);
                        int ind2 = upper_bound(tab[0], 0, tab[0].size() - 1, b);
                        ans += tab[0].size() - ind2;
                    }
                }
                max = Math.max(max, ans);
                ans = 0;
                for (int j = 0; j < tab[2].size(); j++) {
                    int a = tab[2].get(j);
                    int ind = upper_bound(tab[0], 0, tab[0].size() - 1, a);
                    for (int k = ind; k < tab[0].size(); k++) {
                        int b = tab[0].get(k);
                        int ind2 = upper_bound(tab[1], 0, tab[1].size() - 1, b);
                        ans += tab[1].size() - ind2;
                    }
                }
                max = Math.max(max, ans);
                ans = 0;
                for (int j = 0; j < tab[2].size(); j++) {
                    int a = tab[2].get(j);
                    int ind = upper_bound(tab[1], 0, tab[1].size() - 1, a);
                    for (int k = ind; k < tab[1].size(); k++) {
                        int b = tab[1].get(k);
                        int ind2 = upper_bound(tab[0], 0, tab[0].size() - 1, b);
                        ans += tab[0].size() - ind2;
                    }
                }
                max = Math.max(max, ans);
                out.println(max);
            }
        }

        void sieve() {
            isPrime.set(0);
            isPrime.set(1);
            for (int i = 2; i < isPrime.size(); i++) {
                if (!isPrime.get((int) i)) {
                    primes.add(i);
                    for (long j = 2 * i; j < isPrime.size(); j += i) {
                        isPrime.set((int) j);
                    }
                }
            }
        }

        Set<Integer> divs(int n) {
            Map<Integer, Integer> map = primeFactors(n);
            Set<Integer> res = new HashSet<>();
            res.add(1);
            int ans = 1;
            for (int key : map.keySet()) {
                Set<Integer> toAdd = new HashSet<>();
                for (int a : res) {
                    for (int i = 1; i <= map.get(key); i++) {
                        toAdd.add((int) (a * pow(key, i)));
                    }
                }
                res.addAll(toAdd);
            }
            return res;
        }

        Map<Integer, Integer> primeFactors(int n) {
            Map<Integer, Integer> res = new HashMap<>();
            int index = 0;
            int PF = primes.get(index);
            while (PF * PF <= n) {
                while (n % PF == 0) {
                    n /= PF;
                    if (!res.containsKey(PF)) {
                        res.put(PF, 1);
                    } else {
                        res.put(PF, res.get(PF) + 1);
                    }
                }
                PF = primes.get(++index);
            }
            if (n != 1L) {
                if (!res.containsKey(n)) {
                    res.put(n, 1);
                } else {
                    res.put(n, res.get(n) + 1);
                }
            }
            return res;
        }

        public long pow(long a, int b) {
            long result = 1;
            while (b > 0) {
                if (b % 2 != 0) {
                    result *= a;
                    b--;
                }
                a *= a;
                b /= 2;
            }

            return result;

        }

        public int upper_bound(ArrayList<Integer> tab, int l, int h, long x) {
            while (l < h) {
                int mid = (l + h) / 2;
                if (tab.get(mid) == x) {
                    return mid;
                } else if (tab.get(mid) < x) {
                    l = mid + 1;
                } else {
                    h = mid;
                }
            }
            return l;
        }

    }

    static class FastScanner {
        private BufferedReader br;
        private StringTokenizer st;

        public FastScanner(InputStream inputStream) {
            br = new BufferedReader(new InputStreamReader(inputStream));
        }

        public String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}

