문제
수학2 기말을 망쳐 B0를 받은 한별이는 최근 개방된 KSA 예지관에서 "사인은 B0" 노래만 부르고 있다고 한다.
"아나타노 아이도루 사인와 B0!"
한별이는 노래의 박자에 맞춰 $(N+1)\times (N+1)$ 크기의 격자 위에서 댄스를 추기 시작한다.
정수 $A,ドル $B,ドル $C,ドル $N$이 주어졌을 때, $(Ax+By+C)^{N}$에서 $x^{i}y^{j}$의 계수를 $M_{i,j}$이라고 하자. 한별이는 처음에 $(0,0)$ 칸에서 시작하여 다음에 따라 이동할 수 있다.
- 만약 $M_{i,j+1}$이 $M_{i,j}$ 이상인 경우, 한별이는 $(i,j)$에서 $(i,j+1)$으로 이동할 수 있다.
- 만약 $M_{i+1,j}$이 $M_{i,j}$ 이상인 경우, 한별이는 $(i,j)$에서 $(i+1,j)$으로 이동할 수 있다.
이때 움직일 수 있는 최장 경로의 길이를 출력하자. 경로의 길이는 한별이가 움직인 횟수와 같다.
출력
각 테스트 케이스에 대해 한별이가 격자 위에서 움직일 수 있는 최장 경로의 길이를 출력한다.
제한
- 1ドル \leq T \leq 100$
- 1ドル \leq A, B, C, N \leq 10^{9}$
서브태스크
| 번호 | 배점 | 제한 | | 1 | 5 | $A= B = C = 1;$ $N \leq 500$
|
| 2 | 40 | $A,B,C, N \leq 2 \times 10^{5}$
|
| 3 | 55 | 추가 제약 조건 없음
|
주어진 예시에 대해, 한별이의 가능한 경로를 나타낸 그림이다.
W3sicHJvYmxlbV9pZCI6IjMxNDM4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMGFjXHVjNzc4XHVjNzQwIEIwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMyMThcdWQ1NTkyIFx1YWUzMFx1YjlkMFx1Yzc0NCBcdWI5ZGRcdWNjZDAgQjBcdWI5N2MgXHViYzFiXHVjNzQwIFx1ZDU1Y1x1YmNjNFx1Yzc3NFx1YjI5NCBcdWNkNWNcdWFkZmMgXHVhYzFjXHViYzI5XHViNDFjIEtTQSBcdWM2MDhcdWM5YzBcdWFkMDBcdWM1ZDBcdWMxMWMgJnF1b3Q7XHVjMGFjXHVjNzc4XHVjNzQwIEIwJnF1b3Q7IFx1YjE3OFx1Yjc5OFx1YjljYyBcdWJkODBcdWI5NzRcdWFjZTAgXHVjNzg4XHViMmU0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gPFwvcD5cclxuXHJcbjxibG9ja3F1b3RlPlxyXG48cD4mcXVvdDtcdWM1NDRcdWIwOThcdWQwYzBcdWIxNzggXHVjNTQ0XHVjNzc0XHViM2M0XHViOGU4IFx1YzBhY1x1Yzc3OFx1YzY0MCBCMCEmcXVvdDs8XC9wPlxyXG48XC9ibG9ja3F1b3RlPlxyXG5cclxuPHA+XHVkNTVjXHViY2M0XHVjNzc0XHViMjk0IFx1YjE3OFx1Yjc5OFx1Yzc1OCBcdWJjMTVcdWM3OTBcdWM1ZDAgXHViOWRlXHVjZGIwICQoTisxKVxcdGltZXMgKE4rMSkkIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWFjYTlcdWM3OTAgXHVjNzA0XHVjNWQwXHVjMTFjIFx1YjMwNFx1YzJhNFx1Yjk3YyBcdWNkOTRcdWFlMzAgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4MTVcdWMyMTggJEEkLCAkQiQsICRDJCwgJE4kXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsICQoQXgrQnkrQylee059JFx1YzVkMFx1YzExYyAkeF57aX15XntqfSRcdWM3NTggXHVhY2M0XHVjMjE4XHViOTdjICRNX3tpLGp9JFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWM3OTAuIFx1ZDU1Y1x1YmNjNFx1Yzc3NFx1YjI5NCBcdWNjOThcdWM3NGNcdWM1ZDAgJCgwLDApJCBcdWNlNzhcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTU4XHVjNWVjIFx1YjJlNFx1Yzc0Y1x1YzVkMCBcdWI1MzBcdWI3N2MgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIDxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlx1YjljY1x1YzU3ZCAkTV97aSxqKzF9JFx1Yzc3NCAkTV97aSxqfSQgXHVjNzc0XHVjMGMxXHVjNzc4IFx1YWNiZFx1YzZiMCwgXHVkNTVjXHViY2M0XHVjNzc0XHViMjk0ICQoaSxqKSRcdWM1ZDBcdWMxMWMgJChpLGorMSkkXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiA8XC9saT5cclxuXHQ8bGk+XHViOWNjXHVjNTdkICRNX3tpKzEsan0kXHVjNzc0ICRNX3tpLGp9JCBcdWM3NzRcdWMwYzFcdWM3NzggXHVhY2JkXHVjNmIwLCBcdWQ1NWNcdWJjYzRcdWM3NzRcdWIyOTQgJChpLGopJFx1YzVkMFx1YzExYyAkKGkrMSxqKSRcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIDxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1Yzc3NFx1YjU0YyBcdWM2YzBcdWM5YzFcdWM3N2MgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWM3YTUgXHVhY2JkXHViODVjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWM3OTAuIFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVkNTVjXHViY2M0XHVjNzc0XHVhYzAwIFx1YzZjMFx1YzljMVx1Yzc3OCBcdWQ2OWZcdWMyMThcdWM2NDAgXHVhYzE5XHViMmU0LiA8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWQ1NThcdWIwOTggXHVjNzc0XHVjMGMxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggJFQkXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIDxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIxMjQgXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCAkQSQsICRCJCwgJEMkLCAkTiRcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1ZDU1Y1x1YmNjNFx1Yzc3NFx1YWMwMCBcdWFjYTlcdWM3OTAgXHVjNzA0XHVjNWQwXHVjMTFjIFx1YzZjMFx1YzljMVx1Yzc3YyBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YzdhNSBcdWFjYmRcdWI4NWNcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDEgXFxsZXEgVCBcXGxlcSAxMDAkPFwvbGk+XHJcblx0PGxpPiQxIFxcbGVxIEEsIEIsIEMsIE4gXFxsZXEgMTBeezl9JDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD4kQT0gQiA9IEMgPSAxOyQgJE4gXFxsZXEgNTAwJDxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+JEEsQixDLCBOIFxcbGVxIDIgXFx0aW1lcyAxMF57NX0kPFwvcD5cclxuIiwic3VidGFzazMiOiI8cD5cdWNkOTRcdWFjMDAgXHVjODFjXHVjNTdkIFx1Yzg3MFx1YWM3NCBcdWM1YzZcdWM3NGM8XC9wPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdS5hY21pY3BjLm5ldFwvMTA2NGZhNDQtODkxMS00MjA0LWIzZjItNTY1M2Q5OTBmZDE0XC8lRUMlODIlQUMlRUMlOUQlQjglRUMlOUQlODBiMDMucG5nXCIgc3R5bGU9XCJoZWlnaHQ6IDI1OXB4OyB3aWR0aDogNDAwcHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzhmY1x1YzViNFx1YzljNCBcdWM2MDhcdWMyZGNcdWM1ZDAgXHViMzAwXHVkNTc0LCBcdWQ1NWNcdWJjYzRcdWM3NzRcdWM3NTggXHVhYzAwXHViMmE1XHVkNTVjIFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjggXHVhZGY4XHViOWJjXHVjNzc0XHViMmU0LjxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjMxNDM4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU2lnbiBpcyBCMCIsImRlc2NyaXB0aW9uIjoiPHA+SGFuYnllb2wsIHdobyBmYWlsZWQgdGhlIE1hdGhlbWF0aWNzIDImbmJzcDtmaW5hbCBleGFtJm5ic3A7YW5kIHJlY2VpdmVkIGEgZ3JhZGUgb2YmbmJzcDtCMCwgaXMgc2FpZCB0byBiZSBzaW5naW5nIHRoZSBzb25nICZxdW90O1NpZ24gaXMgQjAmcXVvdDsmbmJzcDthdCB0aGUgcmVjZW50bHkgb3BlbmVkIEtTQSBZZWppIEhhbGwuPFwvcD5cclxuXHJcbjxibG9ja3F1b3RlPlxyXG48cD4mcXVvdDtBbmF0YSBubyZuYnNwO2FpZG9ydSBTYWluIHdhIEIwISZxdW90OzxcL3A+XHJcbjxcL2Jsb2NrcXVvdGU+XHJcblxyXG48cD5IYW5ieWVvbCBzdGFydHMgZGFuY2luZyB0byB0aGUgcmh5dGhtIG9uIHRoZSBncmlkIG9mIGRpbWVuc2lvbiAkKE4rMSkgXFx0aW1lcyAoTisxKSQuPFwvcD5cclxuXHJcbjxwPkdpdmVuIGludGVnZXJzICRBJCwgJEIkLCAkQyQsIGFuZCAkTiQsIGxldCAkTV97aSxqfSQgYmUgdGhlIGNvZWZmaWNpZW50IG9mICR4XntpfXlee2p9JCBmb3IgdGhlIGNvZWZmaWNpZW50cyBvZiAkKEF4K0J5K0MpXntOfSQuJm5ic3A7SGFuYnllb2wgZGFuY2VzIG9uIHRoZSBncmlkIGJ5IGZvbGxvd2luZyB0aGUgZ2l2ZW4gcnVsZXMsIHN0YXJ0aW5nIGZyb20gY2VsbCAkKDAsMCkkLjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPklmICRNX3tpLGorMX0kIGlzIGdyZWF0ZXIgdGhhbiBvciBlcXVhbCB0byAkTV97aSxqfSQsIEhhbmJ5ZW9sIGNhbiBtb3ZlIGZyb20gJChpLGopJCB0byAkKGksaisxKSQuPFwvbGk+XHJcblx0PGxpPklmICRNX3tpKzEsan0kIGlzIGdyZWF0ZXIgdGhhbiBvciBlcXVhbCB0byAkTV97aSxqfSQsIEhhbmJ5ZW9sIGNhbiBtb3ZlIGZyb20gJChpLGopJCB0byAkKGkrMSxqKSQuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+UHJpbnQgdGhlIGxlbmd0aCBvZiB0aGUgbG9uZ2VzdCBwYXRoIHRoYXQgY2FuIGJlIG1vdmVkLiBUaGUgbGVuZ3RoIG9mIHRoZSBwYXRoIGlzIGVxdWFsIHRvIHRoZSBudW1iZXIgb2YgdGltZXMgSGFuYnllb2wgbW92ZXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5FYWNoIHRlc3QgY29udGFpbnMgbXVsdGlwbGUgdGVzdCBjYXNlcy4gVGhlIGZpcnN0IGxpbmUgY29udGFpbnMgYW4mbmJzcDtpbnRlZ2VyICRUJCwmbmJzcDt0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMuJm5ic3A7VGhlIGRlc2NyaXB0aW9uIG9mIHRoZSB0ZXN0IGNhc2VzIGZvbGxvd3MuPFwvcD5cclxuXHJcbjxwPlRoZSBmaXJzdCBsaW5lJm5ic3A7b2YgZWFjaCB0ZXN0IGNhc2UgY29udGFpbnMgZm91ciBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgJEEkLCAkQiQsICRDJCwgYW5kICROJC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHByaW50IHRoZSBsb25nZXN0IHBvc3NpYmxlIGxlbmd0aCBvZiBhbnkgcGF0aCBvbiB0aGUgZ3JpZCZuYnNwO3RoYXQgSGFuYnllb2wgY2FuIG1vdmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4kMSBcXGxlcSBUIFxcbGVxIDEwMCQ8XC9saT5cclxuXHQ8bGk+JDEgXFxsZXEgQSwgQiwgQywgTiBcXGxlcSAxMF57OX0kPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMSI6IjxwPiRBPSBCID0mbmJzcDtDID0gMTskICROIFxcbGVxIDUwMCQ8XC9wPlxyXG4iLCJzdWJ0YXNrMiI6IjxwPiRBLEIsQywgTiBcXGxlcSAyJm5ic3A7XFx0aW1lcyAxMF57NX0kPFwvcD5cclxuIiwic3VidGFzazMiOiI8cD5ObyBhZGRpdGlvbmFsIGNvbnN0cmFpbnRzPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3UuYWNtaWNwYy5uZXRcLzhlZGFmOThhLTY3ZDItNDc5MS05ZGZkLWQwNDRiOGRhNDY5NFwvJUVDJTgyJUFDJUVDJTlEJUI4JUVDJTlEJTgwYjAzLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OiAyNTlweDsgd2lkdGg6IDQwMHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5UaGlzIGlzIGFuIGlsbHVzdHJhdGlvbiBvZiBIYW55YmVvbCYjMzk7cyBwb3NzaWJsZSBwYXRoIGZvciB0aGUgZ2l2ZW4gZXhhbXBsZS48XC9wPlxyXG4ifV0=