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.Arrays;
import java.util.Iterator;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        MyScan in = new MyScan(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskB solver = new TaskB();
        int testCount = Integer.parseInt(in.next());
        for (int i = 1; i <= testCount; i++)
            solver.solve(i, in, out);
        out.close();
    }

    static class TaskB {
        static AList[] pd = new AList[100001];

        static {
            for (int t = 0; t < pd.length; t++) {
                pd[t] = new AList();
            }

            for (int r = 1; r < pd.length; r++) {
                for (int s = r; s < pd.length; s += r) {
                    pd[s].add(r);
                }
            }

        }

        public void solve(int testNumber, MyScan in, PrintWriter out) {

//
            int a = in.nextInt();
            int b = in.nextInt();
            int c = in.nextInt();
//


            int[] l = new int[8];


            int m1 = 0, m2 = 0, m3 = 0;
            while (m1 < pd[a].size() || m2 < pd[b].size() || m3 < pd[c].size()) {
                int r1 = m1 >= pd[a].size() ? 1000000 : pd[a].get(m1);
                int r2 = m2 >= pd[b].size() ? 1000000 : pd[b].get(m2);
                int r3 = m3 >= pd[c].size() ? 1000000 : pd[c].get(m3);


                int min = Math.min(r1, Math.min(r2, r3));

                int cur = 0;
                if (min == r1) {
                    m1++;
                    cur ^= 1;
                }
                if (min == r2) {
                    m2++;
                    cur ^= 2;
                }
                if (min == r3) {
                    m3++;
                    cur ^= 4;
                }
                l[cur]++;

            }

            long res = 0;
            for (int[] ss : new int[][]{{1, 6, 6}, {2, 4, 5}, {3, 4, 5}, {1, 2, 4}, {3, 6, 6}, {5, 6, 6}, {3, 5, 5}, {1, 3, 4}, {2, 3, 4},
                    {3, 3, 4}, {2, 5, 5}, {4, 6, 7}, {6, 6, 7}, {1, 2, 7}, {2, 6, 7}, {1, 4, 6}, {3, 4, 6}, {2, 7, 7}, {3, 5, 6}, {6, 7, 7},
                    {2, 3, 5}, {5, 5, 6}, {4, 7, 7}, {1, 3, 7}, {3, 3, 7}, {1, 5, 6}, {1, 2, 6}, {1, 4, 7}, {3, 4, 7}, {2, 4, 7}, {1, 3, 6},
                    {1, 5, 7}, {2, 3, 6}, {3, 3, 6}, {2, 5, 7}, {3, 5, 7}, {4, 5, 7}, {5, 5, 7}, {1, 6, 7}, {1, 2, 5}, {3, 6, 7}, {5, 6, 7},
                    {1, 7, 7}, {1, 3, 5}, {5, 7, 7}, {2, 3, 7}, {3, 3, 5}, {3, 7, 7}, {7, 7, 7}, {4, 5, 6}, {2, 5, 6}}) {
                res += getRes(l, ss[0], ss[1], ss[2]);
            }

            out.println(res);


        }

        private long getRes(int[] l, int i1, int i2, int i3) {
            long res = 0;
            if (i1 == i2) {
                if (i1 == i3) {
                    res += q(l[i1]);
                } else {
                    res += s(l[i1]) * l[i3];
                }
            } else {
                if (i1 == i3) {
                    res += s(l[i3]) * l[i2];
                } else if (i2 == i3) {
                    res += s(l[i3]) * l[i1];
                } else {
                    res += l[i3] * l[i1] * l[i2];
                }
            }
            return res;
        }

        private long q(long i) {
            return i * (i + 1) * (i + 2) / 6;
        }

        private long s(long i) {
            return i * (i + 1) / 2;
        }

    }

    static class AList implements Iterable<Integer> {
        int[] data;
        int size = 0;

        public AList(int n) {
            this.data = new int[Math.max(Integer.highestOneBit(n - 1) << 1, 4)];
        }

        public AList() {
            this(4);
        }

        public AList(int[] data) {
            this(data.length);
            System.arraycopy(data, 0, this.data, 0, data.length);
            size = data.length;
        }

        AList(int[] data, int s) {
            this.data = data;
            this.size = s;
        }

        public void add(int k) {
            if (size == data.length) {
                data = Arrays.copyOf(data, data.length << 1);
            }
            data[size++] = k;
        }


        public Iterator<Integer> iterator() {


            int[] m = new int[1];
            return new Iterator<Integer>() {

                public boolean hasNext() {
                    return m[0] < AList.this.size;
                }


                public Integer next() {
                    return AList.this.data[m[0]++];
                }
            };
        }


        public String toString() {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < size; i++) {
                sb.append(data[i]).append(' ');
            }
            return sb.toString();
        }

        public int size() {
            return size;
        }

        public int get(int i) {
            return data[i];
        }

    }

    static class MyScan {
        private final InputStream in;
        private byte[] inbuf = new byte[1024];
        public int lenbuf = 0;
        public int ptrbuf = 0;

        public MyScan(InputStream in) {
            this.in = in;
        }

        private int readByte() {
            if (lenbuf == -1) throw new InputMismatchException();
            if (ptrbuf >= lenbuf) {
                ptrbuf = 0;
                try {
                    lenbuf = in.read(inbuf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (lenbuf <= 0) return -1;
            }
            return inbuf[ptrbuf++];
        }

        public boolean isSpaceChar(int c) {
            return !(c >= 33 && c <= 126);
        }

        public int skip() {
            int b;
            while ((b = readByte()) != -1 && isSpaceChar(b)) ;
            return b;
        }

        public String next() {
            int b = skip();
            StringBuilder sb = new StringBuilder();
            while (!(isSpaceChar(b))) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }

        public int nextInt() {
            int num = 0, b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
            if (b == '-') {
                minus = true;
                b = readByte();
            }

            while (true) {
                if (b >= '0' && b <= '9') {
                    num = num * 10 + (b - '0');
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

    }
}

