팬케이크 먹기

오늘 아침 은주는 직육면체 모양의 팬케이크를 만들었다. 팬케이크의 가로, 세로, 높이는 각각 A cm, B cm, C cm이다.

신혜는 이 팬케이크를 D번 먹으려고 한다. 신혜가 한 번 먹을 때마다 은주는 현재 남아 있는 팬케이크를 한 면과 평행하게 잘라, 두께가 정확히 1 cm인 조각 하나를 신혜에게 준다. 은주는 어느 방향으로 자를지 매번 선택할 수 있다.

은주는 원래 팬케이크를 모두 먹고 싶었기 때문에, 신혜가 D번 먹은 뒤에도 가능한 한 많은 양을 남기고 싶다.

A, B, C, D가 주어졌을 때, 신혜가 D번 먹은 뒤 은주가 남길 수 있는 팬케이크 부피의 최댓값을 구하시오.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 빈 줄로 구분될 수 있다.

각 테스트 케이스는 한 줄에 A, B, C, D가 주어진다.

각 테스트 케이스마다 은주가 남길 수 있는 팬케이크 부피의 최댓값을 한 줄에 하나씩 출력한다. 이 값은 부호 있는 64비트 정수 범위 안에 들어온다.

• 0 ≤ D ≤ A + B + C - 3

두 번째 테스트 케이스에서는 먼저 4 × 5 면과 평행하게 두 번 잘라 높이를 6 cm에서 4 cm로 줄일 수 있다. 그다음 4 × 4 면과 평행하게 한 번 더 자르면 남은 팬케이크의 크기는 4 × 4 × 4가 되므로 부피는 64이다.