시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 485 138 116 32.312%

문제

ATM에는 다른 종류 두 가지의 지폐가 굉장히 많이 있다. ATM에서 돈을 찾을 때 ATM은 예금주의 잔액을 넘지 않는 범위에서 정확한 양의 돈을 지급한다. 꿍은 지폐를 많이 들고다니고 싶지 않기때문에 되도록이면 가장 적은 수의 지폐를 들고다니고 싶어한다.

여러분은 가장 적은 수의 지폐로 꿍이 인출하려는 금액을 정확히 지급해주는 ATM을 만들어야 한다. ATM을 만들 때, ATM안에는 무제한으로 지폐가 들어있다고 가정해도 좋다.

입력

첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있으며 각 줄에는 a, b(ATM에 있는 지폐의 종류)와 S(꿍이 인출하려는 금액) 세개의 정수로 이루어져 있으며 공백으로 구분되어 있다. (1≤a,b≤10000, a≠b, 0≤S≤109

출력

각 테스트케이스에 대해 ATM에서 인출되는 두 가지 지폐의 장수를 각각 출력한다. 만약 가능한 경우가 없다면 "Impossible" (따옴표 제외)이라고 출력한다.

예제 입력 1

3
1 10 23
3 2 7
4 6 2

예제 출력 1

3 2
1 2
Impossible
W3sicHJvYmxlbV9pZCI6Ijc0ODEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJBVE1cdWIxODBcdWM3NzQiLCJkZXNjcmlwdGlvbiI6IjxwPkFUTVx1YzVkMFx1YjI5NCBcdWIyZTRcdWI5NzgmbmJzcDtcdWM4ODVcdWI5NTggXHViNDUwJm5ic3A7XHVhYzAwXHVjOWMwXHVjNzU4IFx1YzljMFx1ZDNkMFx1YWMwMCBcdWFkNDlcdWM3YTVcdWQ3ODggXHViOWNlXHVjNzc0IFx1Yzc4OFx1YjJlNC4gQVRNXHVjNWQwXHVjMTFjIFx1YjNjOFx1Yzc0NCBcdWNjM2VcdWM3NDQgXHViNTRjIEFUTVx1Yzc0MCBcdWM2MDhcdWFlMDhcdWM4ZmNcdWM3NTggXHVjNzk0XHVjNTYxXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTQgXHViYzk0XHVjNzA0XHVjNWQwXHVjMTFjIFx1YzgxNVx1ZDY1NVx1ZDU1YyBcdWM1OTFcdWM3NTggXHViM2M4XHVjNzQ0IFx1YzljMFx1YWUwOVx1ZDU1Y1x1YjJlNC4gXHVhZmNkXHVjNzQwIFx1YzljMFx1ZDNkMFx1Yjk3YyBcdWI5Y2VcdWM3NzQgXHViNGU0XHVhY2UwXHViMmU0XHViMmM4XHVhY2UwIFx1YzJmNlx1YzljMCBcdWM1NGFcdWFlMzBcdWI1NGNcdWJiMzhcdWM1ZDAgXHViNDE4XHViM2M0XHViODVkXHVjNzc0XHViYTc0IFx1YWMwMFx1YzdhNSBcdWM4MDFcdWM3NDAgXHVjMjE4XHVjNzU4IFx1YzljMFx1ZDNkMFx1Yjk3YyBcdWI0ZTRcdWFjZTBcdWIyZTRcdWIyYzhcdWFjZTAgXHVjMmY2XHVjNWI0XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1ZWNcdWI3ZWNcdWJkODRcdWM3NDAgXHVhYzAwXHVjN2E1IFx1YzgwMVx1Yzc0MCBcdWMyMThcdWM3NTggXHVjOWMwXHVkM2QwXHViODVjIFx1YWZjZFx1Yzc3NCZuYnNwO1x1Yzc3OFx1Y2Q5Y1x1ZDU1OFx1YjgyNFx1YjI5NCZuYnNwO1x1YWUwOFx1YzU2MVx1Yzc0NCBcdWM4MTVcdWQ2NTVcdWQ3ODgmbmJzcDtcdWM5YzBcdWFlMDlcdWQ1NzRcdWM4ZmNcdWIyOTQgQVRNXHVjNzQ0IFx1YjljY1x1YjRlNFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIEFUTVx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHViNTRjLCBBVE1cdWM1NDhcdWM1ZDBcdWIyOTQgXHViYjM0XHVjODFjXHVkNTVjXHVjNzNjXHViODVjIFx1YzljMFx1ZDNkMFx1YWMwMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyZTRcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTc0XHViM2M0IFx1Yzg4Ylx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWNcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCBcdWFjMDEgXHVjOTA0XHVjNWQwXHViMjk0IGEsJm5ic3A7YihBVE1cdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzljMFx1ZDNkMFx1Yzc1OCBcdWM4ODVcdWI5NTgpXHVjNjQwIFMoXHVhZmNkXHVjNzc0IFx1Yzc3OFx1Y2Q5Y1x1ZDU1OFx1YjgyNFx1YjI5NCBcdWFlMDhcdWM1NjEpIFx1YzEzOFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4mbmJzcDsoMSZsZTthLGImbGU7MTAwMDAsIGEmbmU7YiwgMCZsZTtTJmxlOzEwPHN1cD45PFwvc3VwPikmbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCBBVE1cdWM1ZDBcdWMxMWMgXHVjNzc4XHVjZDljXHViNDE4XHViMjk0IFx1YjQ1MCBcdWFjMDBcdWM5YzAgXHVjOWMwXHVkM2QwXHVjNzU4IFx1YzdhNVx1YzIxOFx1Yjk3YyBcdWFjMDFcdWFjMDEgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVhYzAwXHViMmE1XHVkNTVjIFx1YWNiZFx1YzZiMFx1YWMwMCBcdWM1YzZcdWIyZTRcdWJhNzQgJnF1b3Q7SW1wb3NzaWJsZSZxdW90OyAoXHViNTMwXHVjNjM0XHVkNDVjIFx1YzgxY1x1YzY3OClcdWM3NzRcdWI3N2NcdWFjZTAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijc0ODEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBdXRvbWF0aWMgQ2FzaCBUZXJtaW5hbCIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGF1dG9tYXRpYyB0ZWxsZXIgbWFjaGluZSAoQVRNKSBoYXMgYSBsb3Qgb2YgYmFua25vdGVzIG9mIHR3byBkaWZmZXJlbnQgdmFsdWVzLiBXaGVuIGFwZXJzb24gd2hvIHVzZXMgdGhlIHRlcm1pbmFsIHJlcXVlc3RzIHNvbWUgYW1vdW50LCB0aGUgbWFjaGluZSBpc3N1ZXMgZXhhY3RseSB0aGlzIGFtb3VudCBvZiBtb25leSAob2YgY291cnNlLCBpZiB0aGlzIGFtb3VudCBkb2VzIG5vdCBleGNlZWQgYSBiYWxhbmNlIG9mIHRoZSB1c2VyJmxzcXVvO3MgYWNjb3VudCkuIE1vc3QgcGVvcGxlIGRvIG5vdCBsaWtlIHRvIGNhcnJ5IGEgaHVnZSBidW5kbGUgb2YgYmFua25vdGVzLCB0aGVyZWZvcmUgdGhlIG1hY2hpbmUgbXVzdCBpc3N1ZSByZXF1ZXN0ZWQgYW1vdW50IHVzaW5nIG1pbmltYWwgcG9zc2libGUgbnVtYmVyIG9mIGJhbmtub3Rlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+WW91ciB0YXNrIGlzIHRvIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IGRldGVybWluZXMgdGhlIG51bWJlciBvZiBiYW5rbm90ZXMgb2YgZWFjaCB2YWx1ZSB0aGF0IHNob3VsZCBiZSBpc3N1ZWQgYnkgdGhlIG1hY2hpbmUgc28gdGhhdCB0aGUgdXNlciByZWNlaXZlcyB0aGUgcmVxdWVzdGVkIGFtb3VudCBhbmQgdGhlIHRvdGFsIG51bWJlciBvZiBiYW5rbm90ZXMgaXMgbWluaW1hbC4gWW91IG1heSBhc3N1bWUgdGhhdCB0aGUgbnVtYmVyIG9mIGJhbmtub3RlcyBvZiBlYWNoIHZhbHVlIGlzIG5vdCBsaW1pdGVkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IG51bWJlciBpbiB0aGUgaW5wdXQgZ2l2ZXMgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBBIHNpbmdsZSBsaW5lIGZvciBlYWNoIGNhc2UgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMgYSwgYiAodGhlIHZhbHVlcyBvZiBiYW5rbm90ZXMgaW4gdGhlIG1hY2hpbmUpIGFuZCBTICh0aGUgYW1vdW50IG9mIG1vbmV5IHJlcXVlc3RlZCBieSB0aGUgdXNlcikuICgxJmxlO2EsYiZsZTsxMDAwMCwgYSZuZTtiLCAwJmxlO1MmbGU7MTA8c3VwPjk8XC9zdXA+KS4gSW50ZWdlcnMgaW4gZWFjaCBsaW5lIGFyZSBzZXBhcmF0ZWQgYnkgYSBzcGFjZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UgcHJpbnQgYSBzaW5nbGUgbGluZSBpbiB0aGUgb3V0cHV0IHdpdGggdHdvIGludGVnZXJzICZuZGFzaDsgbnVtYmVycyBvZiBiYW5rbm90ZXMgb2YgZWFjaCB2YWx1ZSB3aGljaCBtdXN0IGJlIGlzc3VlZCBieSBBVE0uIEluIGNhc2Ugd2hlbiBpdCZsc3F1bztzIG5vdCBwb3NzaWJsZSB0byBpc3N1ZSByZXF1ZXN0ZWQgYW1vdW50LCBwcmludCB0aGUgd29yZCAmcXVvdDtJbXBvc3NpYmxlJnF1b3Q7ICh3aXRob3V0IHF1b3RlcykuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d