31289번 - 기부왕의 님게임

문제

기부와 택구는 더 나은 세상을 만들기 위해 기부를 하려고 하는데, 평범하게 기부하면 재미가 없으니 유명한 게임인 님 게임을 이용해 기부하기로 했다.

님 게임이란, 여러 개의 돌 더미가 주어지고 두 사람이 번갈아 가면서 하나의 더미를 선택해 원하는 개수만큼 돌을 1개 이상 제거하다가 전체 돌 더미의 마지막 돌을 가져가는 사람이 승리하는 게임이다.

두 사람은 정확히 세 개의 돌 더미가 있는 님 게임을 할 예정이다. 이번 님 게임은 기부가 목적인 게임이므로 특별히 가져가는 돌 하나 당 10ドル,000円$원을 기부하기로 했다. 두 사람은 님 게임을 잘 알아서 최적의 전략을 알고 있으며, 스포츠맨십이 뛰어나서 이길 수 있는 게임에서 일부러 지는 경우는 없다. 그러면서도 각자 자신이 최대한 많은 금액을 기부하려고 할 때, 게임이 끝나고 두 사람이 기부할 금액을 구해보자.

이때 게임은 항상 기부가 먼저 시작하는 것으로 한다.

입력

첫째 줄에 님 게임을 하는 횟수 $T$가 주어진다. $(1\le T \le 100,000円)$

다음 줄부터 $T$개의 줄에 각 게임에 쓰이는 세 돌 더미의 돌의 개수 $x,ドル $y,ドル $z$가 공백으로 구분되어 주어진다. $(1\le x,y,z \le 200)$

출력

각 게임마다, 기부와 택구의 기부금을 공백으로 구분하여 한 줄에 하나씩 출력한다.

제한

힌트