시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 128 MB 271 79 58 30.366%

문제

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

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

힌트