시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 10941 2259 1745 23.385%

문제

최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M 과 N 보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 <x:y>와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다. <x:y>의 다음 해를 표현한 것을 <x':y'>이라고 하자. 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. <M:N>은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다. 

예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11 번째 해는 <1:11>로 표현된다. <3:1>은 13 번째 해를 나타내고, <10:12>는 마지막인 60 번째 해를 나타낸다. 

네 개의 정수 M, N, x 와 y가 주어질 때, <M:N>이 카잉 달력의 마지막 해라고 하면 <x:y>는 몇 번째 해를 나타내는 지를 구하는 프로그램을 작성하라. 

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. 각 줄에는 네 개의 정수 M, N, x와 y가 주어진다. (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N) 여기서 <M:N>은 카잉 달력의 마지막 해를 나타낸다.

출력

출력은 표준 출력을 사용한다. 각 테스트 데이터에 대해, 정수 k를 한 줄에 출력한다. 여기서 k는 <x:y>가 k번째 해를 나타내는 것을 의미한다. 만일 <x:y>에 의해 표현되는 해가 없다면, 즉, <x:y>가 유효하지 않은 표현이면, -1을 출력한다.

예제 입력 1

3
10 12 3 9
10 12 7 2
13 11 5 6

예제 출력 1

33
-1
83

힌트

W3sicHJvYmxlbV9pZCI6IjYwNjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNlNzRcdWM3ODkgXHViMmVjXHViODI1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWNkNWNcdWFkZmNcdWM1ZDAgSUNQQyBcdWQwZDBcdWMwYWNcdWIzMDBcdWIyOTQgXHViMGE4XHVjNTQ0XHViYTU0XHViOWFjXHVjZTc0XHVjNzU4IFx1Yzc4OVx1Y2U3NCBcdWM4MWNcdWFkNmRcdWM3NzQgXHViMTgwXHViNzdjXHVjNmI0IFx1YmIzOFx1YmE4NVx1Yzc0NCBcdWM5YzBcdWIyY2MgXHVjZTc0XHVjNzg5IFx1YzgxY1x1YWQ2ZFx1Yzc0NCBcdWQxYTBcdWIzMDBcdWI4NWMgXHVkNTU4XHVjNWVjIFx1YzEzOFx1YzZjY1x1Yzg0Y1x1YjJlNFx1YjI5NCBcdWMwYWNcdWMyZTRcdWM3NDQgXHViYzFjXHVhY2FjXHVkNTg4XHViMmU0LiBcdWNlNzRcdWM3ODkgXHVjODFjXHVhZDZkXHVjNzU4IFx1YmMzMVx1YzEzMVx1YjRlNFx1Yzc0MCBcdWQyYjlcdWM3NzRcdWQ1NWMgXHViMmVjXHViODI1XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU1YyBcdWFjODNcdWM3M2NcdWI4NWMgXHVjNTRjXHViODI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViNGU0XHVjNzQwIE0gXHVhY2ZjIE4gXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWM3OTBcdWM1ZjBcdWMyMTggeCwgeVx1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVhYzAxIFx1YjE0NFx1YjNjNFx1Yjk3YyAmbHQ7eDp5Jmd0O1x1YzY0MCBcdWFjMTlcdWM3NDAgXHVkNjE1XHVjMmRkXHVjNzNjXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU1OFx1YzYwMFx1YjJlNC4gXHVhZGY4XHViNGU0XHVjNzQwIFx1Yzc3NCBcdWMxMzhcdWMwYzFcdWM3NTggXHVjMmRjXHVjZDA4XHVjNWQwIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1ZDU3NFx1Yjk3YyAmbHQ7MToxJmd0O1x1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1NThcdWFjZTAsIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVkNTc0XHViOTdjICZsdDsyOjImZ3Q7XHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU1OFx1YzYwMFx1YjJlNC4gJmx0O3g6eSZndDtcdWM3NTggXHViMmU0XHVjNzRjIFx1ZDU3NFx1Yjk3YyBcdWQ0NWNcdWQ2MDRcdWQ1NWMgXHVhYzgzXHVjNzQ0ICZsdDt4JiMzOTs6eSYjMzk7Jmd0O1x1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWM3OTAuIFx1YjljY1x1Yzc3YyB4Jm5ic3A7Jmx0OyBNIFx1Yzc3NFx1YmE3NCB4JiMzOTsgPSB4ICsgMVx1Yzc3NFx1YWNlMCwgXHVhZGY4XHViODA3XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3NCB4JiMzOTsgPSAxXHVjNzc0XHViMmU0LiBcdWFjMTlcdWM3NDAgXHViYzI5XHVjMmRkXHVjNzNjXHViODVjIFx1YjljY1x1Yzc3YyB5ICZsdDsgTlx1Yzc3NFx1YmE3NCB5JiMzOTsgPSB5ICsgMVx1Yzc3NFx1YWNlMCwgXHVhZGY4XHViODA3XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3NCB5JiMzOTsgPSAxXHVjNzc0XHViMmU0LiAmbHQ7TTpOJmd0O1x1Yzc0MCBcdWFkZjhcdWI0ZTQgXHViMmVjXHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWQ1NzRcdWI4NWNcdWMxMWMsIFx1Yzc3NCBcdWQ1NzRcdWM1ZDAgXHVjMTM4XHVjMGMxXHVjNzU4IFx1Yzg4NVx1YjlkMFx1Yzc3NCBcdWIzYzRcdWI3OThcdWQ1NWNcdWIyZTRcdWIyOTQgXHVjNjA4XHVjNWI4XHVjNzc0IFx1YzgwNFx1ZDU3NCBcdWM2MjhcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIE0gPSAxMCBcdWM3NzRcdWFjZTAgTiA9IDEyXHViNzdjXHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWQ1NzRcdWIyOTQgJmx0OzE6MSZndDtcdWI4NWMgXHVkNDVjXHVkNjA0XHViNDE4XHVhY2UwLCAxMSBcdWJjODhcdWM5ZjggXHVkNTc0XHViMjk0ICZsdDsxOjExJmd0O1x1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWI0MWNcdWIyZTQuICZsdDszOjEmZ3Q7XHVjNzQwIDEzIFx1YmM4OFx1YzlmOCBcdWQ1NzRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHVhY2UwLCAmbHQ7MTA6MTImZ3Q7XHViMjk0IFx1YjljOFx1YzljMFx1YjljOVx1Yzc3OCA2MCBcdWJjODhcdWM5ZjggXHVkNTc0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHViMTI0IFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggTSwgTiwgeCBcdWM2NDAgeVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzggXHViNTRjLCAmbHQ7TTpOJmd0O1x1Yzc3NCBcdWNlNzRcdWM3ODkgXHViMmVjXHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWQ1NzRcdWI3N2NcdWFjZTAgXHVkNTU4XHViYTc0ICZsdDt4OnkmZ3Q7XHViMjk0IFx1YmE4NyBcdWJjODhcdWM5ZjggXHVkNTc0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM5YzBcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWI3N2MuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjUmbmJzcDtcdWIzNzBcdWM3NzRcdWQxMzBcdWIyOTQgXHVkNDVjXHVjOTAwIFx1Yzc4NVx1YjgyNVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc0MCBUXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWIzNzBcdWM3NzRcdWQxMzBcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDFjXHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNzg1XHViODI1IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzgxNVx1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWIzNzBcdWM3NzRcdWQxMzBcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MWNcdWIyZTQuIFx1YWMwMSBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMTI0IFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggTSwgTiwgeFx1YzY0MCB5XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBNLCBOICZsZTsgNDAsMDAwLCAxICZsZTsgeCAmbGU7IE0sIDEgJmxlOyB5ICZsZTsgTikgXHVjNWVjXHVhZTMwXHVjMTFjICZsdDtNOk4mZ3Q7XHVjNzQwIFx1Y2U3NFx1Yzc4OSBcdWIyZWNcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1ZDU3NFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDljXHViODI1XHVjNzQwIFx1ZDQ1Y1x1YzkwMCBcdWNkOWNcdWI4MjVcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTVjXHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1YzVkMCBcdWIzMDBcdWQ1NzQsIFx1YzgxNVx1YzIxOCBrXHViOTdjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM1ZWNcdWFlMzBcdWMxMWMga1x1YjI5NCAmbHQ7eDp5Jmd0O1x1YWMwMCBrXHViYzg4XHVjOWY4IFx1ZDU3NFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNzdjICZsdDt4OnkmZ3Q7XHVjNWQwIFx1Yzc1OFx1ZDU3NCBcdWQ0NWNcdWQ2MDRcdWI0MThcdWIyOTQgXHVkNTc0XHVhYzAwIFx1YzVjNlx1YjJlNFx1YmE3NCwgXHVjOTg5LCAmbHQ7eDp5Jmd0O1x1YWMwMCBcdWM3MjBcdWQ2YThcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzQwIFx1ZDQ1Y1x1ZDYwNFx1Yzc3NFx1YmE3NCwgLTFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjYwNjQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDYWluIENhbGVuZGFyIiwiZGVzY3JpcHRpb24iOiI8cD5JdCB3YXMgcmVjZW50bHkgcmV2ZWFsZWQgYnkgdGhlIElDUEMgZXhjYXZhdGlvbiB0ZWFtIHRoYXQgdGhlIEluY2EgRW1waXJlIHdhcyBlc3RhYmxpc2hlZCBqdXN0IGFmdGVyIHRoZSBDYWluIEVtcGlyZSB3aGljaCB3YXMgYSBzcGxlbmRpZCBjaXZpbGl6YXRpb24gdGhhdCBmbG91cmlzaGVkIGluIFNvdXRoIEFtZXJpY2EuIEl0IGlzIGJlbGlldmVkIHRoYXQgdGhlIHBlb3BsZSBpbiB0aGUgQ2FpbiBFbXBpcmUgdXNlZCBhbiBpbnRlcmVzdGluZyBvZGQgY2FsZW5kYXIuIEluIHRoZWlyIGNhbGVuZGFyLCBhIHllYXIgd2FzIHJlcHJlc2VudGVkIGJ5ICZsdDt4OnkmZ3Q7LCB3aGVyZSB4IGFuZCB5IGFyZSBuYXR1cmFsIG51bWJlcnMgd2hpY2ggYXJlIGxlc3MgdGhhbiBvciBlcXVhbCB0byBNIGFuZCBOLCByZXNwZWN0aXZlbHkuIFRoZSBmaXJzdCB5ZWFyLCB0aGF0IGlzLCB0aGUgYmVnaW5uaW5nIG9mIHRoZSB3b3JsZCBpcyByZXByZXNlbnRlZCBieSAmbHQ7MToxJmd0Oy4gVGhlIHNlY29uZCB5ZWFyIGlzIHJlcHJlc2VudGVkIGJ5ICZsdDsyOjImZ3Q7LiBMZXQgJmx0O3gmIzM5Ozp5JiMzOTsmZ3Q7YmUgdGhlIGZvbGxvd2luZyB5ZWFyIG9mICZsdDt4OnkmZ3Q7LiBJZiB4ICZsdDsgTSwgeCYjMzk7ID0geCArIDEsIG90aGVyd2lzZSB4JiMzOTsgPSAxLiBTaW1pbGFybHksIGlmIHkgJmx0OyBOLCB5JiMzOTsgPSB5ICsgMSwgb3RoZXJ3aXNlIHkmIzM5OyA9IDEuIFRoZSBsYXN0IHllYXIgb2YgdGhlaXIgY2FsZW5kYXIgaXMgJmx0O006TiZndDsuIEl0IGlzIHNhaWQgdGhhdCB0aGVyZSB3YXMgYSBwcm9waGVjeSB3aGljaCBzdGF0ZXMgdGhlIHdvcmxkIGVuZHMgaW4gdGhlIHllYXIgJmx0O006TiZndDsuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBhc3N1bWUgdGhhdCBNID0gMTAgYW5kIE4gPSAxMi4gVGhlIGZpcnN0IHllYXIgaXMgcmVwcmVzZW50ZWQgYnkgJmx0OzE6MSZndDsuIFRoZSB5ZWFyICZsdDsxOjExJmd0OyByZXByZXNlbnRzIHRoZSAxMTxzdXA+dGg8XC9zdXA+IHllYXIsICZsdDszOjEmZ3Q7IHJlcHJlc2VudHMgdGhlIDEzPHN1cD50aDxcL3N1cD4geWVhciwgYW5kICZsdDsxMDoxMiZndDsgcmVwcmVzZW50cyB0aGUgNjA8c3VwPnRoPFwvc3VwPiB5ZWFyIHdoaWNoIGlzIHRoZSBsYXN0IHllYXIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkdpdmVuIGZvdXIgaW50ZWdlcnMgTSwgTiwgeCwgYW5kIHksIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IGNvbXB1dGVzIHRoZSBudW1iZXIgayBzdWNoIHRoYXQgJmx0O3g6eSZndDsgcmVwcmVzZW50cyB0aGUgazxzdXA+dGg8XC9zdXA+IHllYXIsIHdoZXJlICZsdDt4OnkmZ3Q7IGlzIHRoZSBsYXN0IHllYXIgb2YgdGhlIHdvcmxkIGluIHRoZSBDYWluIENhbGVuZGFyLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSBjb25zaXN0cyBvZiBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgZm91ciBpbnRlZ2VycyBNLCBOLCB4LCBhbmQgeSAoMSAmbGU7IE0sTiAmbGU7IDQwIDAwMCwgMSAmbGU7IHggJmxlOyBNLCAxICZsZTsgeSAmbGU7IE4pLCB3aGVyZSAmbHQ7TTpOJmd0OyBpcyB0aGUgbGFzdCB5ZWFyIG9mIHRoZSB3b3JsZCBpbiB0aGUgQ2FpbiBDYWxlbmRhci48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCBleGFjdGx5IG9uZSBsaW5lIGZvciBlYWNoIHRlc3QgY2FzZS4gVGhlIGxpbmUgc2hvdWxkIGNvbnRhaW4gYW4gaW50ZWdlciBrLCB3aGVyZSB0aGUgazxzdXA+dGg8XC9zdXA+IHllYXIgaXMgcmVwcmVzZW50ZWQgYnkgJmx0O3g6eSZndDsgZm9yIHggYW5kIHkgZ2l2ZW4gaW4gdGhlIGlucHV0LiBJZiB0aGVyZSBkb2VzbiZyc3F1bzt0IGV4aXN0IGEgeWVhciByZXByZXNlbnRlZCBieSAmbHQ7eDp5Jmd0OywgcHJpbnQgLTEuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d