WoodArt 사는 나무를 이용하여 여러 가지 조각품을 만드는 회사로 유명하다. 이 회사에서 일하는 세계적인 조각가 Mr. Kube 씨는 요즘 다양한 크기의 정육면체의 나무 조각들만을 이용하여 멋진 조형물을 만들기 위해 많은 시간을 투자하고 있다. </p>

WoodArt 사에 공급되는 원목은 가로, 세로, 높이의 길이가 각각 W, L, H 인 직육면체인데, Mr. Kube 씨는 우선 이 원목을 잘라 모든 조각이 정육면체가 되도록 만든다. 나무를 정교하게 자르기 위해 그는 한 순간에 나무 한 조각을 잘라 두 개의 직육면체를 얻는다. 즉, 원목을 잘라 두 개의 직육면체를 얻고, 그 각각의 직육면체를 다시 자르는 작업을 반복하여 모든 나무 조각이 정육면체가 될 때까지 자른다. 그런데, 그는 직육면체의 원목을 받아 모든 조각이 정육면체가 될 때까지 절단하되, 절단 회수를 최소로 하길 원한다.

원목의 크기를 나타내는 W, L, H 값들은 각각 1 이상 200 이하의 정수이며, 최종적으로 얻어진 모든 정육면체의 한 변의 길이도 1 이상인 정수가 되도록 절단한다.

나무를 자르는 과정에서 발생할 수 있는 길이의 손실은 무시하기로 한다. 아래 그림에서 보인 것처럼, 자르기 전의 나무 조각의 크기가 W, L, H 이고, 절단한 후 두 조각의 크기가 각각 W, L, H1과 W, L, H2라면 H = H1 + H2 라고 가정한다. W와 L에 대해서도 동일하게 적용된다.

입력 형식

입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 20) 가 주어진다. 각 테스트 케이스에 대해 원목의 크기를 나타내는 W,L,H (1 ≤ W, L, H ≤ 200) 값이 한 줄에 주어진다. 

출력 형식

출력은 표준출력(standard output)을 통하여 출력한다. 각 테스트 케이스에 대해, 절단 횟수를 최소로 하여 자를 경우 생성되는 정육면체 조각들의 개수를 한 줄에 출력한다.

예제 입력

3
15 5 5
2 4 3
5 6 6

예제 출력

3
10
13