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.BufferedInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class B3 {
/*
 * 
2
9 6 8 
49 15 60

41
126
 */
	static int A,B,C;
	public static void main(String[] args) {
		JS in = new JS();
		PrintWriter out = new PrintWriter(System.out);

		//System.out.println(factor(100).toString());
		int T = in.nextInt();
		int haveA[] = new int[100001];
		int haveB[] = new int[100001];
		int haveC[] = new int[100001];
		for(int runs = 1; runs <= T; runs++) {
			A = in.nextInt();
			B = in.nextInt();
			C = in.nextInt();
			ArrayList<Integer> af = factor(A);
			ArrayList<Integer> bf = factor(B);
			ArrayList<Integer> cf = factor(C);
			//System.out.println(af.toString());
			//System.out.println(bf.toString());
			//System.out.println(cf.toString());

			for(Integer ii : af)haveA[ii]=runs;
			for(Integer ii : bf)haveB[ii]=runs;
			for(Integer ii : cf)haveC[ii]=runs;
			int AB,AC,BC,ABC,N,AA,BB,CC;
			AB=AC=BC=ABC=N=AA=BB=CC=0;
			for(Integer ii : af) {
				if(haveB[ii]==runs && haveC[ii]==runs)ABC++;
				if(haveB[ii]==runs) AB++;
				if(haveC[ii]==runs) AC++;
			}
			for(Integer ii : bf) if(haveC[ii]==runs) BC++;
			
			for(Integer ii : af) if(!(haveB[ii]==runs) && !(haveC[ii]==runs))AA++;
			for(Integer ii : bf) if(!(haveA[ii]==runs) && !(haveC[ii]==runs))BB++;
			for(Integer ii : cf) if(!(haveB[ii]==runs) && !(haveA[ii]==runs))CC++;

			//System.out.println(AB+" "+AC+" "+BC+" "+ABC+" "+AA+" "+BB+" "+CC);
			//System.out.println(choose(ABC,3)*5);
			long res = af.size()*bf.size()*cf.size();
			//System.out.println("Res: "+res);
			res -= 2*ABC*(ABC-1);
			res -= choose(ABC,3)*5; //ABC choose 3

			//res -= (AB-ABC)*(AB-1)*(cf.size());
			//res -= (AC-ABC)*(AC-1)*(bf.size());
			//res -= (BC-ABC)*(BC-1)*(af.size());
			res -= go(AB-ABC, AB)*cf.size();
			res -= go(AC-ABC, AC)*bf.size();
			res -= go(BC-ABC, BC)*af.size();

			//res -= (N*(ABC-1)*(ABC));
			
			res -= (AA *(ABC-1)*(ABC))/2;
			res -= (BB *(ABC-1)*(ABC))/2;
			res -= (CC *(ABC-1)*(ABC))/2;
			
//			ArrayList<trip> ll = new ArrayList<trip>();
//			for(Integer aa : af) {
//				for(Integer bb : bf) {
//					for(Integer cc : cf) {
//						ll.add(new trip(aa,bb,cc));
//					}
//				}
//			}
//			Collections.sort(ll);
//			trip prev = null;
//			for(trip t : ll) {
//				if(prev != null && t.compareTo(prev) == 0) {
//					System.out.println(t+" !");
//				}
//				else System.out.println(t);
//				prev=t;
//			}

			out.println(res);
		}
		out.close();
		
	}
	
	static long go(int a, int b) {
		int curAdd = b-1;
		long res = 0;
		for(int i = 0; i < a; i++) {
			res += curAdd;
			curAdd--;
		}
		return res;
	}
	
	static class trip implements Comparable<trip>{
		int r[];
		public trip(int a, int b, int c) {
			r = new int[] {a,b,c};
			Arrays.sort(r);
		}
		@Override
		public int compareTo(trip o) {
			for(int i = 0; i < 3; i++) {
				if(r[i] < o.r[i]) return -1;
				if(r[i] > o.r[i]) return 1;
			}
			return 0;
		}
		@Override
		public String toString() {
			return "("+r[0]+", "+r[1]+", "+r[2]+")";
		}
		
	}
	
	static long choose(long n, long k) {
		  long prev = 1;
		  for(long c = 1; c <= k; c++)
		    prev = (prev*(n-c+1))/c;
		  return prev;
		}
	
	static ArrayList<Integer> factor(int val){
		ArrayList<Integer> res = new ArrayList<Integer>();
		res.add(1);
		for(int i = 2; i*i <= val; i++) {
			if(val%i==0) {
				res.add(i);
				if(i*i != val) res.add(val/i);
			}
		}
		if(val!=1)res.add(val);
		return res;
	}
	
	
	static class JS{
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;
		
		public JS() {
			in = new BufferedInputStream(System.in, BS);
		}
		
		public JS(String s) throws FileNotFoundException {
			in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
		}
		
		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}				
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}
		
		public int nextInt() {
			return (int)nextLong();
		}
		
		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}
		
		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}
		
		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}
		
		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
	}
}
