Zathras

2025년, 행성 Zathras에는 반쯤 지능을 가진 로봇인 Zathrinian만이 살고 있다. Zathrinian은 두 종류로 나뉘는데, acrobot과 bouncoid이다. 해마다 Great Mind는 그 해의 Great Decision을 내려 Zathrinian이 어떻게 번식하고 어떻게 해체될지 정한다. Great Decision을 내릴 때 Great Mind는 두 가지 영원한 매개변수 α와 β를 고려한다. 이 매개변수는 영원하므로 해가 바뀌어도 변하지 않는다.

번식: Great Mind가 Great Decision을 내릴 때 acrobot이 A마리, bouncoid가 B마리 있다면, Great Mind는 acrobot 한 마리와 bouncoid 한 마리를 짝지어 K = min(A, B)개의 번식 쌍을 만든다. 짝을 이루지 못한 로봇은 그대로 남는다. 다음 날, 이 K쌍 중 2%(내림)가 각각 Zathrinian 한 마리를 낳는다.

태어난 Zathrinian 중 α%(내림)는 acrobot이고 β%(내림)는 bouncoid이다. 나머지 Zathrinian은 acrobot과 bouncoid에 똑같이 나누어 배정하고, 홀수라면 남는 한 마리는 bouncoid가 된다.

해체: Great Mind가 Great Decision을 내릴 때 acrobot의 1%(내림)와 bouncoid의 1%(내림)가 해체 대상으로 지정된다. 이틀 뒤 이 로봇들은 모두 분해된다. 1%는 새 Zathrinian이 태어나기 전인 Great Decision 당일에 계산한다.

Great Decision이 내려지고(1일차), 번식이 일어나고(2일차), 운 없는 Zathrinian이 분해된 뒤(3일차), 세계는 Eternal Specification에 정해진 시각에 다음 해 Great Decision이 열릴 때까지 조화롭게 돌아간다.

acrobot 12345마리와 bouncoid 12890마리로 시작하면 acrobot 123마리와 bouncoid 128마리가 해체 대상이 된다. 쌍의 수는 min(12345, 12890) = 12345이고, 그해에 246마리의 새끼가 태어난다. α=10, β=13이라면 해마다 bouncoid가 더 많이 태어난다. 새끼 중 24마리는 acrobot(246의 10%, 내림), 31마리는 bouncoid(246의 13%, 내림)이고, 나머지 191마리는 acrobot 95마리와 bouncoid 96마리로 나뉜다.

정리하면 acrobot 12345마리와 bouncoid 12890마리로 시작해 하루 뒤에는 acrobot 12464마리와 bouncoid 13017마리가 된다. 그다음 날에는 acrobot 12341마리와 bouncoid 12889마리가 된다. 99년 뒤에는 acrobot 11993마리와 bouncoid 12676마리가 된다. 총 5049년이 지나면 acrobot 3099마리와 bouncoid 3199마리만 남아 전체 개체 수가 크게 줄어든다. 그 뒤로는 개체 수가 영원히 그대로 유지된다.

A, B, α, β, Y가 주어질 때 Y년이 끝난 시점의 acrobot과 bouncoid 개체 수를 구할 수 있는가?

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

각 테스트 케이스마다 "Case #x: AY BY" 형식의 한 줄을 출력한다. x는 테스트 케이스 번호(1부터 시작)이고, (AY, BY)는 Y년 뒤 acrobot과 bouncoid의 개체 수이다.

• 1 ≤ T ≤ 100.
• 0 ≤ α.
• 0 ≤ β.
• α + β ≤ 100.