시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 135 32 27 25.962%

문제

이론물리학자들은 '삶, 우주, 그리고 모든 것'에 대한 질문의 궁극적인 해답이 42라고 생각하지 않았다. (은하수를 여행하는 히치하이커를 위한 안내서 中 한 내용) 대신 양의 정수 A와 B를 나눈 결과에 그 답이 있을것이라 생각했다!

A와 B를 나누는 것은 보기 보다 쉽지 않다. 특히 그 수가 커지면 빠르게 구하기는 더욱 어려워진다. 구식 컴퓨터를 써서 이것을 간단히 구현한다면 엄청엄청 오래걸릴 것이다.

이론물리학자들을 위해 영리한 프로그래머인 당신이 도와주도록 하자.

입력

첫 줄에 테스트케이스 T가 주어진다. (1 <= T <= 200)

각 테스트케이스마다 첫 줄에 N과 M을 입력받는다. N과 M은 각각 수열 A와 B의 길이이다. (1 <= N, M<= 110,000)

그리고 다음 두 줄 중 첫째 줄에 A를 이루는 정수들이 공백으로 구분되어 입력되고(0 < A0, A1 … An <= 1,000,000), 둘째 줄에 B를 이루는 정수들이 입력된다.(0 < B0, B1 … Bm <= 1,000,000) 

A = A0*A1*...*An, B = B0*B1*...*Bn 이다.

출력

각 테스트케이스마다 한줄에 수열 A를 수열 B로 나눈 결과를 기약분수의 형태 "X / Y" 로 예제와 같이 출력한다. (숫자와 구분자 사이에 공백이 있다) X와 Y는 32비트 정수 범위 내이다.

기약분수란 분자와 분모를 최대공약수로 나누어 더이상 약분되지 않는 분수를 말한다.

예제 입력 1

2
3 1
2 4 5
12
2 4
1 15
5 1 7 2

예제 출력 1

Case #1: 10 / 3
Case #2: 3 / 14
W3sicHJvYmxlbV9pZCI6IjkzNjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQwNzAgXHViMDk4XHViMjE3XHVjMTQ4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3NzRcdWI4NjBcdWJiM2NcdWI5YWNcdWQ1NTlcdWM3OTBcdWI0ZTRcdWM3NDAmbmJzcDsmIzM5O1x1YzBiNiwgXHVjNmIwXHVjOGZjLCBcdWFkZjhcdWI5YWNcdWFjZTAgXHViYWE4XHViNGUwIFx1YWM4MyYjMzk7XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM5YzhcdWJiMzhcdWM3NTggXHVhZDgxXHVhZGY5XHVjODAxXHVjNzc4IFx1ZDU3NFx1YjJmNVx1Yzc3NCA0Mlx1Yjc3Y1x1YWNlMCBcdWMwZGRcdWFjMDFcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNTU4XHViMmU0LiZuYnNwOyhcdWM3NDBcdWQ1NThcdWMyMThcdWI5N2MgXHVjNWVjXHVkNTg5XHVkNTU4XHViMjk0IFx1ZDc4OFx1Y2U1OFx1ZDU1OFx1Yzc3NFx1Y2VlNFx1Yjk3YyBcdWM3MDRcdWQ1NWMgXHVjNTQ4XHViMGI0XHVjMTFjIFx1NGUyZCBcdWQ1NWMgXHViMGI0XHVjNmE5KSZuYnNwO1x1YjMwMFx1YzJlMCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IEFcdWM2NDAgQlx1Yjk3YyBcdWIwOThcdWIyMDggXHVhY2IwXHVhY2ZjXHVjNWQwIFx1YWRmOCBcdWIyZjVcdWM3NzQgXHVjNzg4XHVjNzQ0XHVhYzgzXHVjNzc0XHViNzdjIFx1YzBkZFx1YWMwMVx1ZDU4OFx1YjJlNCE8XC9wPlxyXG5cclxuPHA+QVx1YzY0MCBCXHViOTdjIFx1YjA5OFx1YjIwNFx1YjI5NCZuYnNwO1x1YWM4M1x1Yzc0MCBcdWJjZjRcdWFlMzAmbmJzcDtcdWJjZjRcdWIyZTQgXHVjMjdkXHVjOWMwIFx1YzU0YVx1YjJlNC4gXHVkMmI5XHVkNzg4IFx1YWRmOCBcdWMyMThcdWFjMDAgXHVjZWU0XHVjOWMwXHViYTc0IFx1YmU2MFx1Yjk3NFx1YWM4YyBcdWFkNmNcdWQ1NThcdWFlMzBcdWIyOTQmbmJzcDtcdWIzNTRcdWM2YjEgXHVjNWI0XHViODI0XHVjNmNjXHVjOWM0XHViMmU0LiBcdWFkNmNcdWMyZGQgXHVjZWY0XHVkNGU4XHVkMTMwXHViOTdjIFx1YzM2OFx1YzExYyZuYnNwO1x1Yzc3NFx1YWM4M1x1Yzc0NCBcdWFjMDRcdWIyZThcdWQ3ODgmbmJzcDtcdWFkNmNcdWQ2MDRcdWQ1NWNcdWIyZTRcdWJhNzQgXHVjNWM0XHVjY2FkXHVjNWM0XHVjY2FkIFx1YzYyNFx1Yjc5OFx1YWM3OFx1YjliNCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1Yjg2MFx1YmIzY1x1YjlhY1x1ZDU1OVx1Yzc5MFx1YjRlNFx1Yzc0NCBcdWM3MDRcdWQ1NzQgXHVjNjAxXHViOWFjXHVkNTVjIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1Yjc5OFx1YmEzOFx1Yzc3OCZuYnNwO1x1YjJmOVx1YzJlMFx1Yzc3NCBcdWIzYzRcdWM2NDBcdWM4ZmNcdWIzYzRcdWI4NWQgXHVkNTU4XHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTQgVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7KDEgJmx0Oz0gVCAmbHQ7PSAyMDApPFwvcD5cclxuXHJcbjxwPlx1YWMwMSZuYnNwO1x1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWNjYWIgXHVjOTA0XHVjNWQwIE5cdWFjZmMgTVx1Yzc0NCBcdWM3ODVcdWI4MjVcdWJjMWJcdWIyOTRcdWIyZTQuIE5cdWFjZmMgTVx1Yzc0MCBcdWFjMDFcdWFjMDEgXHVjMjE4XHVjNWY0IEFcdWM2NDAgQlx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM3NzRcdWIyZTQuJm5ic3A7KDEgJmx0Oz0gTiwgTSZsdDs9IDExMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjlhY1x1YWNlMCBcdWIyZTRcdWM3NGMgXHViNDUwIFx1YzkwNCBcdWM5MTEgXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBBXHViOTdjIFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWM4MTVcdWMyMThcdWI0ZTRcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM3ODVcdWI4MjVcdWI0MThcdWFjZTAoMCAmbHQ7IEEwLCBBMSAmaGVsbGlwOyBBbiAmbHQ7PSAxLDAwMCwwMDApLCBcdWI0NThcdWM5ZjgmbmJzcDtcdWM5MDRcdWM1ZDAgQlx1Yjk3YyBcdWM3NzRcdWI4ZThcdWIyOTQgXHVjODE1XHVjMjE4XHViNGU0XHVjNzc0IFx1Yzc4NVx1YjgyNVx1YjQxY1x1YjJlNC4oMCAmbHQ7IEIwLCBCMSAmaGVsbGlwOyBCbSAmbHQ7PSAxLDAwMCwwMDApJm5ic3A7PFwvcD5cclxuXHJcbjxwPkEgPSBBMCpBMSouLi4qQW4sIEIgPSBCMCpCMSouLi4qQm4gXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVkNTVjXHVjOTA0XHVjNWQwIFx1YzIxOFx1YzVmNCBBXHViOTdjIFx1YzIxOFx1YzVmNCBCXHViODVjIFx1YjA5OFx1YjIwOCBcdWFjYjBcdWFjZmNcdWI5N2MgXHVhZTMwXHVjNTdkXHViZDg0XHVjMjE4XHVjNzU4IFx1ZDYxNVx1ZDBkYyAmcXVvdDtYIFwvIFkmcXVvdDsmbmJzcDtcdWI4NWMgXHVjNjA4XHVjODFjXHVjNjQwIFx1YWMxOVx1Yzc3NCZuYnNwO1x1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gKFx1YzIyYlx1Yzc5MFx1YzY0MCBcdWFkNmNcdWJkODRcdWM3OTAgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YWNmNVx1YmMzMVx1Yzc3NCBcdWM3ODhcdWIyZTQpJm5ic3A7WFx1YzY0MCBZXHViMjk0IDMyXHViZTQ0XHVkMmI4IFx1YzgxNVx1YzIxOCBcdWJjOTRcdWM3MDQgXHViMGI0XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFlMzBcdWM1N2RcdWJkODRcdWMyMThcdWI3ODAgXHViZDg0XHVjNzkwXHVjNjQwIFx1YmQ4NFx1YmFhOFx1Yjk3YyBcdWNkNWNcdWIzMDBcdWFjZjVcdWM1N2RcdWMyMThcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0IFx1YjM1NFx1Yzc3NFx1YzBjMSBcdWM1N2RcdWJkODRcdWI0MThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YmQ4NFx1YzIxOFx1Yjk3YyBcdWI5ZDBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTM2MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJpZyBEaXZpc2lvbiIsImRlc2NyaXB0aW9uIjoiPHA+QSB0aGVvcmV0aWNhbCBwaHlzaWNpc3QgZnJpZW5kIGlzIGRvaW5nIHJlc2VhcmNoIGFib3V0IHRoZSAmcXVvdDtBbnN3ZXIgdG8gdGhlIFVsdGltYXRlIFF1ZXN0aW9uIG9mIExpZmUsIHRoZSBVbml2ZXJzZSwgYW5kIEV2ZXJ5dGhpbmcmcXVvdDssIGhlIHRoaW5rcyB0aGF0IGl0IGlzIG5vdCA0MiBhcyBzdWdnZXN0ZWQgYnkgJmxkcXVvO1RoZSBIaXRjaGhpa2VyJiMzOTtzIEd1aWRlIHRvIHRoZSBHYWxheHkmcmRxdW87IHNjaWVuY2UgZmljdGlvbiBjb21lZHkgc2VyaWVzOyBpbnN0ZWFkIGhlIHRoaW5rcyBpdCBpcyB0aGUgcmVzdWx0IG9mIGRpdmlkaW5nIHRoZSBwcm9kdWN0cyBvZiB0d28gc2VxdWVuY2VzIG9mIHBvc2l0aXZlIGludGVnZXJzIEEgYW5kIEIhJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSB0YXNrIG9mIGNhbGN1bGF0aW5nIHRoZSBwcm9kdWN0IG9mIEEgYW5kIEIgZm9sbG93ZWQgYnkgZGl2aXNpb24gdHVybmVkIG91dCB0byBiZSBub3QgYXMgZWFzeSBhcyBpdCBsb29rcywgc3BlY2lhbGx5IHdpdGggdGhlIHNlcXVlbmNlcyBiZWluZyBsb25nIGFuZCB0aGUgcHJvZHVjdHMgZ2V0dGluZyB0b28gbGFyZ2UgdmVyeSBxdWlja2x5ISBFdmVuIHVzaW5nIGEgbW9kZXJuIGNvbXB1dGVyLCBhIHN0cmFpZ2h0IGZvcndhcmQgaW1wbGVtZW50YXRpb24gZm9yIHRoZSBjYWxjdWxhdGlvbnMgbWF5IHRha2UgdmVyeSBsb25nIHRpbWUgdG8gY29tcGxldGUhIEFuZCB0aGlzIGlzIHdoZXJlIHdlIHNlZWsgeW91ciBoZWxwIGFzIGEgYnJpbGxpYW50IGNvbXB1dGVyIHNjaWVudGlzdCEmbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGFuIGludGVnZXIgKDEgJmx0Oz0gVCAmbHQ7PSAyMDApLCB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMuIFQgdGVzdCBjYXNlcyBmb2xsb3csIHRoZSBmaXJzdCBsaW5lIG9mIGVhY2ggdGVzdCBjYXNlIGNvbnRhaW5zIHR3byBpbnRlZ2VycyAoMSAmbHQ7PSBOLCBNJmx0Oz0gMTEwLDAwMCksIHRoZSBsZW5ndGhzIG9mIHNlcXVlbmNlcyBBIGFuZCBCIHJlc3BlY3RpdmVseS4gVHdvIGxpbmVzIGZvbGxvdywgdGhlIGZpcnN0IGxpbmUgY29udGFpbnMgTiBzcGFjZSBzZXBhcmF0ZWQgaW50ZWdlcnMgKDAgJmx0OyBBMCwgQTEgJmhlbGxpcDsgQW4gJmx0Oz0gMSwwMDAsMDAwKSwgYW5kIHRoZSBzZWNvbmQgbGluZSBjb250YWlucyBNIHNwYWNlIHNlcGFyYXRlZCBpbnRlZ2VycyAoMCAmbHQ7IEIwLCBCMSAmaGVsbGlwOyBCbSAmbHQ7PSAxLDAwMCwwMDApLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgcHJpbnQgb25lIGxpbmUgY29udGFpbmluZyB0aGUgcmVzdWx0IG9mIGRpdmlkaW5nIHRoZSBwcm9kdWN0IG9mIHNlcXVlbmNlIEEgYnkgdGhlIHByb2R1Y3Qgb2Ygc2VxdWVuY2UgQiBhcyBhIHJlZHVjZWQgZnJhY3Rpb24gb2YgdGhlIGZvcm1hdCAmbGRxdW87WCBcLyBZJnJkcXVvOyAoTm90aWNlIHRoZSBzaW5nbGUgc3BhY2UgYmVmb3JlIGFuZCBhZnRlciB0aGUgZnJhY3Rpb24gc2lnbikuIFggYW5kIFkgYXJlIGd1YXJhbnRlZWQgdG8gZml0IGluIDMyLWJpdCBzaWduZWQgaW50ZWdlci4gQSByZWR1Y2VkIGZyYWN0aW9uIGlzIGEgZnJhY3Rpb24gc3VjaCB0aGF0IHRoZSBncmVhdGVzdCBjb21tb24gZGl2aXNvciBiZXR3ZWVuIHRoZSBub21pbmF0b3IgYW5kIHRoZSBkZW5vbWluYXRvciBpcyAxLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==