자트라스

자트라스 행성의 2025년이다. 자트라스는 자트리니안이라고 불리는 반지성 로봇들만 사는 세계이다. 자트리니안에는 애크로봇과 바운코이드라는 두 종류가 있다. 일 년에 한 번, Great Mind는 그해의 Great Decision을 내리고 자트리니안이 어떻게 번식하고 퇴역할지를 정한다. Great Decision을 내릴 때는 α와 β라는 두 Eternal Parameters를 고려한다. 이 매개변수들은 영원불변하므로 해가 바뀌어도 변하지 않는다.

번식: Great Mind가 Great Decision을 내릴 때 애크로봇이 A개이고 바운코이드가 B개라면, Great Mind는 애크로봇 하나와 바운코이드 하나를 짝지어 K = min(A, B)쌍의 번식 쌍을 만든다. 남은 로봇은 모두 짝이 없는 상태가 된다. 다음 날, 그 K쌍 중 2%가 내림하여 계산한 수만큼의 쌍이 각각 새끼 자트리니안 하나를 낳는다.

태어난 모든 새끼 자트리니안 중 α%는 내림하여 계산한 수만큼 애크로봇이 되고, β%는 내림하여 계산한 수만큼 바운코이드가 된다. 나머지 새끼 자트리니안은 애크로봇과 바운코이드로 똑같이 나뉘며, 수가 홀수이면 남는 새끼 하나는 바운코이드가 된다.

퇴역: Great Mind가 Great Decision을 내리면, 애크로봇의 1%와 바운코이드의 1%가 각각 내림하여 계산한 수만큼 퇴역 대상으로 지정된다. 이들은 이틀 뒤에 모두 해체된다. 1%라는 수치는 새로운 자트리니안이 태어나기 전인 Great Decision 당일을 기준으로 계산된다는 점에 유의하라.

Great Decision이 내려지고(1일째), 번식이 이루어지고(2일째), 불운한 자트리니안들이 해체되고 나면(3일째), 온 세상은 다음 해의 Great Decision이 Eternal Specification에 예정된 시각에 이루어질 때까지 조화롭게 계속 기능한다.

예제

애크로봇 12345개와 바운코이드 12890개로 이루어진 개체군에서 시작하면, 애크로봇 123개와 바운코이드 128개가 퇴역 대상으로 지정된다. 쌍의 수는 min(12345, 12890)이고, 이는 12345이다. 따라서 그해에 자손 246개가 태어난다. α=10, β=13라고 하자. 그러면 매년 자트리니안보다 바운코이드가 더 많이 태어난다. 이는 자손 중 24개가 애크로봇이 되고(246의 10%, 내림), 31개가 바운코이드가 되며(246의 13%, 내림), 나머지 191개는 추가 애크로봇 95개와 추가 바운코이드 96개로 나뉜다는 뜻이다.

전체적으로 애크로봇 12345개와 바운코이드 12890개로 시작했다. 하루 뒤에는 애크로봇 12464개와 바운코이드 13017개가 있다. 그다음 날에는 애크로봇 12341개와 바운코이드 12889개가 있다. 99년 뒤에는 애크로봇 11993개와 바운코이드 12676개가 있다. 총 5049년 뒤에는 애크로봇이 불과 3099개, 바운코이드가 3199개만 남으며, 전체 개체군 규모가 엄청나게 감소한다. 그 이후에는 개체군의 크기가 영원히 그대로 유지된다.

A, B, α, β, Y의 값이 주어질 때, Y년이 끝난 시점의 애크로봇과 바운코이드 개체군 크기를 계산할 수 있는가?

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 20초. 메모리 제한: 1 GB. 0 ≤ α. 0 ≤ β. α + β ≤ 100.

작은 데이터 세트 (테스트 세트 1 - 공개)

0 ≤ A ≤ 20000. 0 ≤ B ≤ 20000. 0 ≤ Y ≤ 100.

큰 데이터 세트 (테스트 세트 2 - 비공개)

0 ≤ A ≤ $10^{6}$. 0 ≤ B ≤ $10^{6}$. 0 ≤ Y ≤ $10^{15}$.

입력의 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어진다. 각 줄에는 A, B, α, β, Y라는 5개의 정수가 들어 있다.

각 테스트 케이스마다 "Case #x: $A_{Y}$ $B_{Y}$"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), ($A_{Y}$, $B_{Y}$)는 각각 Y년 후의 애크로봇과 바운코이드 개체군 크기이다.