시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 21 5 5 29.412%

문제

오늘 아침 은주는 팬케익을 만들었다. 자 이제 신혜는 이 팬케익을 먹으려고 한다.

은주가 만든 팬케익은 박스 모양이고, 가로 Acm, 세로 Bcm, 높이 Ccm 크기이다.

신혜는 팬케익을 D번 먹으려고 한다. 매번 신혜가 팬케익을 먹으려고 할 때, 은주는 팬케익을 변에 평행하게 자른 후에 신혜에게 준다.

은주는 뛰어난 요리사이기 때문에, 자르는 케익은 모두 두께가 1cm이다.

원래 은주는 팬케익을 다 먹으려고 했으나, 어쩔수 없이 신혜에게 주는 것이다. 따라서, 최대한 많은 양을 남기려고 한다.

신혜가 팬케익을 D번 먹은 후에 남은 케익의 양은 은주가 케익을 자르는 방법에 따라서 달라지게 된다.

A, B, C, D가 주어졌을 때, 신헤가 팬케익을 D번 먹은 후에 남은 팬케익 부피의 가능한 최대값을 구하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 빈 줄로 구분되며, 다음과 같이 구성되어 있다.

테스트 케이스의 첫째 줄에 A, B, C, D가 주어진다. 0 < A,B,C <= 10^18 이고, 0 <= D <= A+B+C-3 이다.

출력

각 테스트 케이스에 대해 은주가 남길 수 있는 팬케익의 최대 부피를 차례대로 한 줄에 하나씩 출력한다. 이 부피는 부호있는 64비트 정수 범위 안에 들어온다.

예제 입력

3

4 5 6 0

4 5 6 3

1 1 10 9

예제 출력

120
64
1

힌트

두 번째 테스트 케이스를 보자. 왜 정답이 64일까? 가장 먼저 4 * 5 변에 맞춰서 2번 팬케익을 자르면 남은 팬케익은 4*5*4가 된다. 그 다음에 4 * 4 변에 맞추어 팬케익을 자르면 4*4*4가 된다. 따라서 64이다.