종이를 예쁘게 접자
시간 제한1초메모리 제한1024 MB
직사각형 종이의 두 변과 접는 횟수가 주어질 때, 매번 긴 변을 2로 나눈 몫으로 줄여 최종 크기를 구하는 문제입니다.
문제
Dr. Orooji는 책상 위에 365장짜리 일일 달력을 두고 있다. 매일 아침 그는 한 장을 뜯어낸다. 다음 장의 메모를 읽으면서, 습관처럼 손에 든 종이를 접는다. 그는 종이(직사각형)를 항상 긴 변을 따라 접는다. 예를 들어 한 변이 80, 다른 변이 60이면 80인 변을 따라 접어서 40과 60 크기의 종이가 된다. 다시 접을 때는 지금의 긴 변인 60을 따라 접는다.
직사각형 종이와 접는 횟수가 주어질 때, 최종 크기를 구하시오. 길이가 홀수인 변을 접을 때는 나머지를 버린다. 예를 들어 7인 변은 3이 된다.
입력
첫 줄에 데이터 세트의 수를 나타내는 양의 정수 n이 주어진다. 이어지는 n개의 줄에는 각각 직사각형의 두 변과 접는 횟수를 나타내는 양의 정수 3개가 주어진다. 모두 10000 이하이다.
출력
각 데이터 세트마다 먼저 "Data set: v" 형식의 줄을 출력한다. v는 입력된 값이다. 다음 줄에는 직사각형의 최종 값을 출력하되, 큰 변을 먼저 쓴다. 각 테스트 케이스의 출력 뒤에는 빈 줄을 하나 남긴다.