시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 480 135 115 32.303%

문제

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+XHJcblxyXG48cD5cdWM1ZWNcdWI3ZWNcdWJkODRcdWM3NDAgXHVhYzAwXHVjN2E1IFx1YzgwMVx1Yzc0MCBcdWMyMThcdWM3NTggXHVjOWMwXHVkM2QwXHViODVjIFx1YWZjZFx1Yzc3NCZuYnNwO1x1Yzc3OFx1Y2Q5Y1x1ZDU1OFx1YjgyNFx1YjI5NCZuYnNwO1x1YWUwOFx1YzU2MVx1Yzc0NCBcdWM4MTVcdWQ2NTVcdWQ3ODgmbmJzcDtcdWM5YzBcdWFlMDlcdWQ1NzRcdWM4ZmNcdWIyOTQgQVRNXHVjNzQ0IFx1YjljY1x1YjRlNFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIEFUTVx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHViNTRjLCBBVE1cdWM1NDhcdWM1ZDBcdWIyOTQgXHViYjM0XHVjODFjXHVkNTVjXHVjNzNjXHViODVjIFx1YzljMFx1ZDNkMFx1YWMwMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyZTRcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTc0XHViM2M0IFx1Yzg4Ylx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1Y1x1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwIFx1YWMwMSBcdWM5MDRcdWM1ZDBcdWIyOTQgYSwmbmJzcDtiKEFUTVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjOWMwXHVkM2QwXHVjNzU4IFx1Yzg4NVx1Yjk1OClcdWM2NDAgUyhcdWFmY2RcdWM3NzQgXHVjNzc4XHVjZDljXHVkNTU4XHViODI0XHViMjk0IFx1YWUwOFx1YzU2MSkgXHVjMTM4XHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiZuYnNwOygxJmxlO2EsYiZsZTsxMDAwMCwgYSZuZTtiLCAwJmxlO1MmbGU7MTA8c3VwPjk8XC9zdXA+KSZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0IEFUTVx1YzVkMFx1YzExYyBcdWM3NzhcdWNkOWNcdWI0MThcdWIyOTQgXHViNDUwIFx1YWMwMFx1YzljMCBcdWM5YzBcdWQzZDBcdWM3NTggXHVjN2E1XHVjMjE4XHViOTdjIFx1YWMwMVx1YWMwMSBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVhY2JkXHVjNmIwXHVhYzAwIFx1YzVjNlx1YjJlNFx1YmE3NCAmcXVvdDtJbXBvc3NpYmxlJnF1b3Q7IChcdWI1MzBcdWM2MzRcdWQ0NWMgXHVjODFjXHVjNjc4KVx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNzQ4MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkF1dG9tYXRpYyBDYXNoIFRlcm1pbmFsIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgYXV0b21hdGljIHRlbGxlciBtYWNoaW5lIChBVE0pIGhhcyBhIGxvdCBvZiBiYW5rbm90ZXMgb2YgdHdvIGRpZmZlcmVudCB2YWx1ZXMuIFdoZW4gYXBlcnNvbiB3aG8gdXNlcyB0aGUgdGVybWluYWwgcmVxdWVzdHMgc29tZSBhbW91bnQsIHRoZSBtYWNoaW5lIGlzc3VlcyBleGFjdGx5IHRoaXMgYW1vdW50IG9mIG1vbmV5IChvZiBjb3Vyc2UsIGlmIHRoaXMgYW1vdW50IGRvZXMgbm90IGV4Y2VlZCBhIGJhbGFuY2Ugb2YgdGhlIHVzZXImbHNxdW87cyBhY2NvdW50KS4gTW9zdCBwZW9wbGUgZG8gbm90IGxpa2UgdG8gY2FycnkgYSBodWdlIGJ1bmRsZSBvZiBiYW5rbm90ZXMsIHRoZXJlZm9yZSB0aGUgbWFjaGluZSBtdXN0IGlzc3VlIHJlcXVlc3RlZCBhbW91bnQgdXNpbmcgbWluaW1hbCBwb3NzaWJsZSBudW1iZXIgb2YgYmFua25vdGVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Zb3VyIHRhc2sgaXMgdG8gd3JpdGUgYSBwcm9ncmFtIHRoYXQgZGV0ZXJtaW5lcyB0aGUgbnVtYmVyIG9mIGJhbmtub3RlcyBvZiBlYWNoIHZhbHVlIHRoYXQgc2hvdWxkIGJlIGlzc3VlZCBieSB0aGUgbWFjaGluZSBzbyB0aGF0IHRoZSB1c2VyIHJlY2VpdmVzIHRoZSByZXF1ZXN0ZWQgYW1vdW50IGFuZCB0aGUgdG90YWwgbnVtYmVyIG9mIGJhbmtub3RlcyBpcyBtaW5pbWFsLiBZb3UgbWF5IGFzc3VtZSB0aGF0IHRoZSBudW1iZXIgb2YgYmFua25vdGVzIG9mIGVhY2ggdmFsdWUgaXMgbm90IGxpbWl0ZWQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbnVtYmVyIGluIHRoZSBpbnB1dCBnaXZlcyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMuIEEgc2luZ2xlIGxpbmUgZm9yIGVhY2ggY2FzZSBjb250YWlucyB0aHJlZSBpbnRlZ2VycyBhLCBiICh0aGUgdmFsdWVzIG9mIGJhbmtub3RlcyBpbiB0aGUgbWFjaGluZSkgYW5kIFMgKHRoZSBhbW91bnQgb2YgbW9uZXkgcmVxdWVzdGVkIGJ5IHRoZSB1c2VyKS4gKDEmbGU7YSxiJmxlOzEwMDAwLCBhJm5lO2IsIDAmbGU7UyZsZTsxMDxzdXA+OTxcL3N1cD4pLiBJbnRlZ2VycyBpbiBlYWNoIGxpbmUgYXJlIHNlcGFyYXRlZCBieSBhIHNwYWNlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSBwcmludCBhIHNpbmdsZSBsaW5lIGluIHRoZSBvdXRwdXQgd2l0aCB0d28gaW50ZWdlcnMgJm5kYXNoOyBudW1iZXJzIG9mIGJhbmtub3RlcyBvZiBlYWNoIHZhbHVlIHdoaWNoIG11c3QgYmUgaXNzdWVkIGJ5IEFUTS4gSW4gY2FzZSB3aGVuIGl0JmxzcXVvO3Mgbm90IHBvc3NpYmxlIHRvIGlzc3VlIHJlcXVlc3RlZCBhbW91bnQsIHByaW50IHRoZSB3b3JkICZxdW90O0ltcG9zc2libGUmcXVvdDsgKHdpdGhvdXQgcXVvdGVzKS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=