시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 96 44 18 34.615%

문제

해적! 이는 멋진 직업인 것 같지만 큰 고충을 가지는 직업이다. 그 고충 중 하나는 많은 시간을 망망대해에서 지내야 한다는 점이다. 때때로 바람도 불지 않고, 하루종일 아무런 일도 없이 지나가는 날이 있을 수 있는 것이다. 너무 지루하기 때문에 해적들은 금화로 하는 여러가지 놀이를 알고 있다. 그런 놀이 중 하나로 두 명의 해적이 하나의 금화 더미를 이용해서 하는 놀이가 있다. 이 놀이는 두 사람이 서로 차례를 번갈아 바꿔가면서 하는 놀이인데, 각 해적은 자기 차례에 어떤 주어진 정수 K가 주어질 때 K의 제곱수(1, K, K2,...)만큼의 금화를 가져올 수 있다. 마지막 금화를 가져온 해적이 승리한다.

현재 금화 더미에 있는 금화의 개수와 K가 주어질 경우에 어떤 해적이 승리할까?

입력

첫 번째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있으며 두 개의 정수 S와 K로 이루어져 있다. 1 ≤ S ≤ 109, 1 ≤ K ≤ 100을 만족한다. S는 금화의 개수를 의미하여 K는 각 차례에 1, K, K2,...개의 금화를 가져올 수 있다는 의미이다.

출력

각 테스트 케이스 마다 한 줄에 처음 금화를 가져가는 해적이 이기기 위해 첫 번째 차례에 가져가야 하는 금화의 개수의 최솟값을 출력한다. 만약 처음 금화를 가져가는 해적이 어떤 개수의 금화를 가져가도 이길 수 없다면 0을 출력하면 된다.

예제 입력 1

5
5 1
3 2
8 2
50 3
100 10

예제 출력 1

1
0
2
0
1
W3sicHJvYmxlbV9pZCI6IjUzODYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFlMDhcdWQ2NTQgXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9kb3ViLnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDoxMzVweDsgd2lkdGg6MTQxcHhcIiBcLz5cdWQ1NzRcdWM4MDEhIFx1Yzc3NFx1YjI5NCBcdWJhNGJcdWM5YzQgXHVjOWMxXHVjNWM1XHVjNzc4IFx1YWM4MyBcdWFjMTlcdWM5YzBcdWI5Y2MgXHVkMDcwIFx1YWNlMFx1Y2RhOVx1Yzc0NCBcdWFjMDBcdWM5YzBcdWIyOTQgXHVjOWMxXHVjNWM1XHVjNzc0XHViMmU0LiBcdWFkZjggXHVhY2UwXHVjZGE5IFx1YzkxMSBcdWQ1NThcdWIwOThcdWIyOTQgXHViOWNlXHVjNzQwIFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWI5ZGRcdWI5ZGRcdWIzMDBcdWQ1NzRcdWM1ZDBcdWMxMWMgXHVjOWMwXHViMGI0XHVjNTdjIFx1ZDU1Y1x1YjJlNFx1YjI5NCBcdWM4MTBcdWM3NzRcdWIyZTQuIFx1YjU0Y1x1YjU0Y1x1Yjg1YyBcdWJjMTRcdWI3OGNcdWIzYzQgXHViZDg4XHVjOWMwIFx1YzU0YVx1YWNlMCwgXHVkNTU4XHViOGU4XHVjODg1XHVjNzdjIFx1YzU0NFx1YmIzNFx1YjdmMCBcdWM3N2NcdWIzYzQgXHVjNWM2XHVjNzc0IFx1YzljMFx1YjA5OFx1YWMwMFx1YjI5NCBcdWIwYTBcdWM3NzQgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWIxMDhcdWJiMzQgXHVjOWMwXHViOGU4XHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWQ1NzRcdWM4MDFcdWI0ZTRcdWM3NDAgXHVhZTA4XHVkNjU0XHViODVjIFx1ZDU1OFx1YjI5NCBcdWM1ZWNcdWI3ZWNcdWFjMDBcdWM5YzAgXHViMTgwXHVjNzc0XHViOTdjIFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjdmMCBcdWIxODBcdWM3NzQgXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yjg1YyBcdWI0NTAgXHViYTg1XHVjNzU4IFx1ZDU3NFx1YzgwMVx1Yzc3NCBcdWQ1NThcdWIwOThcdWM3NTggXHVhZTA4XHVkNjU0IFx1YjM1NFx1YmJmOFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHVkNTU4XHViMjk0IFx1YjE4MFx1Yzc3NFx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWIxODBcdWM3NzRcdWIyOTQgXHViNDUwIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWMxMWNcdWI4NWMgXHVjYzI4XHViODQwXHViOTdjIFx1YmM4OFx1YWMwOFx1YzU0NCBcdWJjMTRcdWFmZDRcdWFjMDBcdWJhNzRcdWMxMWMgXHVkNTU4XHViMjk0IFx1YjE4MFx1Yzc3NFx1Yzc3OFx1YjM3MCwgXHVhYzAxIFx1ZDU3NFx1YzgwMVx1Yzc0MCBcdWM3OTBcdWFlMzAgXHVjYzI4XHViODQwXHVjNWQwIFx1YzViNFx1YjVhNCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjODE1XHVjMjE4IEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YyBLXHVjNzU4IFx1YzgxY1x1YWNmMVx1YzIxOCgxLCBLLCBLPHN1cD4yPFwvc3VwPiwuLi4pXHViOWNjXHVkMDdjXHVjNzU4IFx1YWUwOFx1ZDY1NFx1Yjk3YyBcdWFjMDBcdWM4MzhcdWM2MmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViOWM4XHVjOWMwXHViOWM5IFx1YWUwOFx1ZDY1NFx1Yjk3YyBcdWFjMDBcdWM4MzhcdWM2MjggXHVkNTc0XHVjODAxXHVjNzc0IFx1YzJiOVx1YjlhY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNjA0XHVjN2FjIFx1YWUwOFx1ZDY1NCBcdWIzNTRcdWJiZjhcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWUwOFx1ZDY1NFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM2NDAgS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzggXHVhY2JkXHVjNmIwXHVjNWQwIFx1YzViNFx1YjVhNCBcdWQ1NzRcdWM4MDFcdWM3NzQgXHVjMmI5XHViOWFjXHVkNTYwXHVhZTRjPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggU1x1YzY0MCBLXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIDEgJmxlOyBTICZsZTsgMTA8c3VwPjk8XC9zdXA+LCAxICZsZTsgSyAmbGU7IDEwMFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NWNcdWIyZTQuIFNcdWIyOTQgXHVhZTA4XHVkNjU0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NThcdWM1ZWMgS1x1YjI5NCBcdWFjMDEgXHVjYzI4XHViODQwXHVjNWQwIDEsIEssIEs8c3VwPjI8XC9zdXA+LC4uLlx1YWMxY1x1Yzc1OCBcdWFlMDhcdWQ2NTRcdWI5N2MgXHVhYzAwXHVjODM4XHVjNjJjIFx1YzIxOCBcdWM3ODhcdWIyZTRcdWIyOTQgXHVjNzU4XHViYmY4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YjljOFx1YjJlNCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1Y2M5OFx1Yzc0YyBcdWFlMDhcdWQ2NTRcdWI5N2MgXHVhYzAwXHVjODM4XHVhYzAwXHViMjk0IFx1ZDU3NFx1YzgwMVx1Yzc3NCBcdWM3NzRcdWFlMzBcdWFlMzAgXHVjNzA0XHVkNTc0IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjYzI4XHViODQwXHVjNWQwIFx1YWMwMFx1YzgzOFx1YWMwMFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVhZTA4XHVkNjU0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVjYzk4XHVjNzRjIFx1YWUwOFx1ZDY1NFx1Yjk3YyBcdWFjMDBcdWM4MzhcdWFjMDBcdWIyOTQgXHVkNTc0XHVjODAxXHVjNzc0IFx1YzViNFx1YjVhNCBcdWFjMWNcdWMyMThcdWM3NTggXHVhZTA4XHVkNjU0XHViOTdjIFx1YWMwMFx1YzgzOFx1YWMwMFx1YjNjNCBcdWM3NzRcdWFlMzggXHVjMjE4IFx1YzVjNlx1YjJlNFx1YmE3NCAwXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTM4NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRvdWJsb29uIEdhbWUiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL2RvdWIucG5nXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjEzNXB4OyB3aWR0aDoxNDFweFwiIFwvPkJlaW5nIGEgcGlyYXRlIG1lYW5zIHNwZW5kaW5nIGEgbG90IG9mIHRpbWUgYXQgc2VhLiBTb21ldGltZXMsIHdoZW4gdGhlcmUgaXMgbm90IG11Y2ggd2luZCwgZGF5cyBjYW4gcGFzcyBieSB3aXRob3V0IGFueSBhY3Rpdml0eS4gVG8gcGFzcyB0aGUgdGltZSBiZXR3ZWVuIGNob3JlcywgcGlyYXRlcyBsaWtlIHRvIHBsYXkgZ2FtZXMgd2l0aCBjb2lucy4gQW4gb2xkIGZhdm9yaXRlIG9mIHRoZSBwaXJhdGVzIGlzIGEgZ2FtZSBmb3IgdHdvIHBsYXllcnMgZmVhdHVyaW5nIG9uZSBzdGFjayBvZiBjb2lucy4gSW4gdHVybiwgZWFjaCBwbGF5ZXIgdGFrZXMgYSBudW1iZXIgb2YgY29pbnMgZnJvbSB0aGUgc3RhY2suIFRoZSBudW1iZXIgb2YgY29pbnMgdGhhdCBhIHBsYXllciB0YWtlcyBtdXN0IGJlIGEgcG93ZXIgb2YgYSBnaXZlbiBpbnRlZ2VyIEsgKDEsIEssIEs8c3VwPjI8XC9zdXA+LCBldGNldGVyYSkuIFRoZSB3aW5uZXIgaXMgdGhlIHBsYXllciB0byB0YWtlIHRoZSBsYXN0IGNvaW4ocykuPFwvcD5cclxuXHJcbjxwPkNhbiB5b3UgaGVscCB0aGUgcGlyYXRlcyBmaWd1cmUgb3V0IGhvdyB0aGUgcGxheWVyIHRvIG1vdmUgY2FuIHdpbiBpbiBhIGdpdmVuIGdhbWUgc2l0dWF0aW9uPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIG51bWJlcjogdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIHRvIGZvbGxvdy4gRWFjaCB0ZXN0IGNhc2UgaGFzIHRoZSBmb2xsb3dpbmcgZm9ybWF0OjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggdHdvIGludGVnZXJzIFMgYW5kIEssIHNhdGlzZnlpbmcgMSAmbGU7IFMgJmxlOyAxMDxzdXA+OTxcL3N1cD4gYW5kIDEgJmxlOyBLICZsZTsgMTAwOiB0aGUgc2l6ZSBvZiB0aGUgc3RhY2sgYW5kIHRoZSBwYXJhbWV0ZXIgSywgcmVzcGVjdGl2ZWx5LjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGV2ZXJ5IHRlc3QgY2FzZSBpbiB0aGUgaW5wdXQsIHRoZSBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gb25lIGludGVnZXIgb24gYSBzaW5nbGUgbGluZTogdGhlIHNtYWxsZXN0IG51bWJlciBvZiBjb2lucyB0aGF0IHRoZSBwbGF5ZXIgdG8gbW92ZSBjYW4gdGFrZSBpbiBvcmRlciB0byBzZWN1cmUgdGhlIHdpbi4gSWYgdGhlcmUgaXMgbm8gd2lubmluZyBtb3ZlLCB0aGUgb3V0cHV0IHNob3VsZCBiZSAwLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==