시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 57 40 39 70.909%

문제

Nim 게임은 몇 개의 돌무더기를 놓고 매 차례마다 각 플레이어가 한 무더기에서 적게는 1개에서부터 많게는 무더기 전체를 가져가는 게임이다. 일반적인 Nim 게임의 승자는 마지막으로 돌을 가져가는 사람이다. 이 게임에서 가장 널리 알려진 전략은 Nim-2-sum을 이용하는 전략이다.

FoodVictory에 신제품 algo90을 납품하던 용태는 FoodVictory의 물류 관리자인 영우의 계속되는 횡포에 견디지 못하고 대결을 신청했다. 영우는 가장 자신있어하는 Nim 게임을 종목으로 선정했고, 용태는 Nim 게임의 전략을 인터넷에 검색했다.

Nim 게임의 전략은 다음과 같다.

두 개의 음이 아닌 정수 X와 Y의 Nim-B-sum (B진법 nim sum)을 NimSum (B, X, Y)라고 하자. 이 값은 다음과 같이 계산할 수 있다.

1) X와 Y를 B진법으로 나타낸다.

2) Nim-B sum의 각 자리 수는 X와 Y의 B진법 표기에서의 각 자리의 합을 B로 나눈 나머지이다.

예를 들면,

NimSum (2, 123, 456) = 1111011 ¤ 111001000 = 110110011 = 435

NimSum (3, 123, 456) = 11120 ¤ 121220 = 102010 = 300

NumSum (4, 123, 456) = 1323 ¤ 13020 = 10303 = 307

일반적인 Nim 게임의 전략은 모든 크기의 돌무더기에 대해 Nim-2 Sum T를 계산하는 것이다. 언제든 용태가 T=0이 되게 차례를 끝낸다면, 용태가 반드시 승리하게 된다. 그리고 영우가 아무리 T를 0이 되지 않게 남긴다고 해도 항상 T를 다시 0으로 만들 수 있는 방법이 존재한다. 이것은 각 무더기마다 NimSum (2, T, PS)로 계산하면 되는데 (PS = 무더기에 있는 돌의 수), 이 값이 PS보다 작다면, PS와 Nim-2 sum의 차이를 구하고, 이 값만큼 돌을 가져가면 된다.

NimSum을 손으로 계산하는 것은 힘들기 때문에 곤란해진 용태를 위해 NimSum (B, X, Y)를 계산하는 프로그램을 짜주자.

입력

입력의 첫 번째 줄에는 테스트 케이스의 수를 나타내는 T가 주어진다. (1 ≤ T ≤ 1000), 그리고 각 테스트 케이스의 첫 줄에는 B, X, Y를 나타내는 정수가 공백을 사이에 두고 주어진다. (2 ≤ B ≤ 2000000, 0 ≤ X ≤ 2000000, 0 ≤ Y ≤ 2000000)

출력

각 테스트 케이스마다 NimSum (B, X, Y)의 10진수 표현을 출력한다.

예제 입력 1

4
2 123 456
3 123 456
4 123 456
5 123 456

예제 출력 1

435
300
307
429
W3sicHJvYmxlbV9pZCI6IjI2ODUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyZDhcdWJlNDRcdWQ1NjkiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdE5pbSBcdWFjOGNcdWM3ODRcdWM3NDAgXHViYTg3IFx1YWMxY1x1Yzc1OCBcdWIzY2NcdWJiMzRcdWIzNTRcdWFlMzBcdWI5N2MgXHViMTkzXHVhY2UwIFx1YjllNCBcdWNjMjhcdWI4NDBcdWI5YzhcdWIyZTQgXHVhYzAxIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YWMwMCBcdWQ1NWMgXHViYjM0XHViMzU0XHVhZTMwXHVjNWQwXHVjMTFjIFx1YzgwMVx1YWM4Y1x1YjI5NCAxXHVhYzFjXHVjNWQwXHVjMTFjXHViZDgwXHVkMTMwIFx1YjljZVx1YWM4Y1x1YjI5NCBcdWJiMzRcdWIzNTRcdWFlMzAgXHVjODA0XHVjY2I0XHViOTdjIFx1YWMwMFx1YzgzOFx1YWMwMFx1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NzRcdWIyZTQuIFx1Yzc3Y1x1YmMxOFx1YzgwMVx1Yzc3OCBOaW0gXHVhYzhjXHVjNzg0XHVjNzU4IFx1YzJiOVx1Yzc5MFx1YjI5NCBcdWI5YzhcdWM5YzBcdWI5YzlcdWM3M2NcdWI4NWMgXHViM2NjXHVjNzQ0IFx1YWMwMFx1YzgzOFx1YWMwMFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1YjExMFx1YjlhYyBcdWM1NGNcdWI4MjRcdWM5YzQgXHVjODA0XHViN2I1XHVjNzQwIE5pbS0yLXN1bVx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NThcdWIyOTQgXHVjODA0XHViN2I1XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRGb29kVmljdG9yeVx1YzVkMCBcdWMyZTBcdWM4MWNcdWQ0ODggYWxnbzkwXHVjNzQ0IFx1YjBhOVx1ZDQ4OFx1ZDU1OFx1YjM1OCBcdWM2YTlcdWQwZGNcdWIyOTQgRm9vZFZpY3RvcnlcdWM3NTggXHViYjNjXHViOTU4IFx1YWQwMFx1YjlhY1x1Yzc5MFx1Yzc3OCBcdWM2MDFcdWM2YjBcdWM3NTggXHVhY2M0XHVjMThkXHViNDE4XHViMjk0IFx1ZDZhMVx1ZDNlY1x1YzVkMCBcdWFjYWNcdWI1MTRcdWM5YzAgXHViYWJiXHVkNTU4XHVhY2UwIFx1YjMwMFx1YWNiMFx1Yzc0NCBcdWMyZTBcdWNjYWRcdWQ1ODhcdWIyZTQuIFx1YzYwMVx1YzZiMFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVjNzkwXHVjMmUwXHVjNzg4XHVjNWI0XHVkNTU4XHViMjk0IE5pbSBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjODg1XHViYWE5XHVjNzNjXHViODVjIFx1YzEyMFx1YzgxNVx1ZDU4OFx1YWNlMCwgXHVjNmE5XHVkMGRjXHViMjk0IE5pbSBcdWFjOGNcdWM3ODRcdWM3NTggXHVjODA0XHViN2I1XHVjNzQ0IFx1Yzc3OFx1ZDEzMFx1YjEzN1x1YzVkMCBcdWFjODBcdWMwYzlcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdE5pbSBcdWFjOGNcdWM3ODRcdWM3NTggXHVjODA0XHViN2I1XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjNzRjXHVjNzc0IFx1YzU0NFx1YjJjYyBcdWM4MTVcdWMyMTggWFx1YzY0MCBZXHVjNzU4IE5pbS1CLXN1bSAoQlx1YzljNFx1YmM5NSBuaW0gc3VtKVx1Yzc0NCBOaW1TdW0gKEIsIFgsIFkpXHViNzdjXHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHVjNzc0IFx1YWMxMlx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YWNjNFx1YzBiMFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQxKSBYXHVjNjQwIFlcdWI5N2MgQlx1YzljNFx1YmM5NVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuPHA+XHJcblx0MikgTmltLUIgc3VtXHVjNzU4IFx1YWMwMSBcdWM3OTBcdWI5YWMgXHVjMjE4XHViMjk0IFhcdWM2NDAgWVx1Yzc1OCBCXHVjOWM0XHViYzk1IFx1ZDQ1Y1x1YWUzMFx1YzVkMFx1YzExY1x1Yzc1OCBcdWFjMDEgXHVjNzkwXHViOWFjXHVjNzU4IFx1ZDU2OVx1Yzc0NCBCXHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWJhNzQsPFwvcD5cclxuPHA+XHJcblx0TmltU3VtICgyLCAxMjMsIDQ1NikgPSAxMTExMDExICZjdXJyZW47IDExMTAwMTAwMCA9IDExMDExMDAxMSA9IDQzNTxcL3A+XHJcbjxwPlxyXG5cdE5pbVN1bSAoMywgMTIzLCA0NTYpID0gMTExMjAgJmN1cnJlbjsgMTIxMjIwID0gMTAyMDEwID0gMzAwPFwvcD5cclxuPHA+XHJcblx0TnVtU3VtICg0LCAxMjMsIDQ1NikgPSAxMzIzICZjdXJyZW47IDEzMDIwID0gMTAzMDMgPSAzMDc8XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNzdjXHViYzE4XHVjODAxXHVjNzc4IE5pbSBcdWFjOGNcdWM3ODRcdWM3NTggXHVjODA0XHViN2I1XHVjNzQwIFx1YmFhOFx1YjRlMCBcdWQwNmNcdWFlMzBcdWM3NTggXHViM2NjXHViYjM0XHViMzU0XHVhZTMwXHVjNWQwIFx1YjMwMFx1ZDU3NCBOaW0tMiBTdW0gVFx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM1YjhcdWM4MWNcdWI0ZTAgXHVjNmE5XHVkMGRjXHVhYzAwIFQ9MFx1Yzc3NCBcdWI0MThcdWFjOGMgXHVjYzI4XHViODQwXHViOTdjIFx1YjA1ZFx1YjBiOFx1YjJlNFx1YmE3NCwgXHVjNmE5XHVkMGRjXHVhYzAwIFx1YmMxOFx1YjRkY1x1YzJkYyBcdWMyYjlcdWI5YWNcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHVjNjAxXHVjNmIwXHVhYzAwIFx1YzU0NFx1YmIzNFx1YjlhYyBUXHViOTdjIDBcdWM3NzQgXHViNDE4XHVjOWMwIFx1YzU0YVx1YWM4YyBcdWIwYThcdWFlMzRcdWIyZTRcdWFjZTAgXHVkNTc0XHViM2M0IFx1ZDU2ZFx1YzBjMSBUXHViOTdjIFx1YjJlNFx1YzJkYyAwXHVjNzNjXHViODVjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YWM4M1x1Yzc0MCBcdWFjMDEgXHViYjM0XHViMzU0XHVhZTMwXHViOWM4XHViMmU0IE5pbVN1bSAoMiwgVCwgUFMpXHViODVjIFx1YWNjNFx1YzBiMFx1ZDU1OFx1YmE3NCBcdWI0MThcdWIyOTRcdWIzNzAgKFBTID0gXHViYjM0XHViMzU0XHVhZTMwXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWIzY2NcdWM3NTggXHVjMjE4KSwgXHVjNzc0IFx1YWMxMlx1Yzc3NCBQU1x1YmNmNFx1YjJlNCBcdWM3OTFcdWIyZTRcdWJhNzQsIFBTXHVjNjQwIE5pbS0yIHN1bVx1Yzc1OCBcdWNjMjhcdWM3NzRcdWI5N2MgXHVhZDZjXHVkNTU4XHVhY2UwLCBcdWM3NzQgXHVhYzEyXHViOWNjXHVkMDdjIFx1YjNjY1x1Yzc0NCBcdWFjMDBcdWM4MzhcdWFjMDBcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHROaW1TdW1cdWM3NDQgXHVjMTkwXHVjNzNjXHViODVjIFx1YWNjNFx1YzBiMFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NDAgXHVkNzk4XHViNGU0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWFjZTRcdWI3ODBcdWQ1NzRcdWM5YzQgXHVjNmE5XHVkMGRjXHViOTdjIFx1YzcwNFx1ZDU3NCBOaW1TdW0gKEIsIFgsIFkpXHViOTdjIFx1YWNjNFx1YzBiMFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjOWRjXHVjOGZjXHVjNzkwLjxcL3A+XHJcblxyXG4iLCJpbnB1dCI6IlxyXG48cD5cclxuXHRcdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IFQgJmxlOyAxMDAwKSwgXHVhZGY4XHViOWFjXHVhY2UwIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgQiwgWCwgWVx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjODE1XHVjMjE4XHVhYzAwIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBCICZsZTsgMjAwMDAwMCwgMCAmbGU7IFggJmxlOyAyMDAwMDAwLCAwICZsZTsgWSAmbGU7IDIwMDAwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgTmltU3VtIChCLCBYLCBZKVx1Yzc1OCAxMFx1YzljNFx1YzIxOCBcdWQ0NWNcdWQ2MDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI2ODUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJOaW0tQiBTdW0iLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBnYW1lIG9mIE5JTSBpcyBwbGF5ZWQgd2l0aCBhbnkgbnVtYmVyIG9mIHBpbGVzIG9mIG9iamVjdHMgd2l0aCBhbnkgbnVtYmVyIG9mIG9iamVjdHMgaW4gZWFjaCBwaWxlLiBBdCBlYWNoIHR1cm4sIGEgcGxheWVyIHRha2VzIG9uZSBvciBtb3JlICh1cCB0byBhbGwpIG9iamVjdHMgZnJvbSBvbmUgcGlsZS4gSW4gdGhlIG5vcm1hbCBmb3JtIG9mIHRoZSBnYW1lLCB0aGUgcGxheWVyIHdobyB0YWtlcyB0aGUgbGFzdCBvYmplY3QgaXMgdGhlIHdpbm5lci4gVGhlcmUgaXMgYSB3ZWxsLWtub3duIHN0cmF0ZWd5IGZvciB0aGlzIGdhbWUgYmFzZWQgb24gdGhlIG5pbS0yIHN1bS48XC9wPlxyXG5cclxuPHA+VGhlIE5pbS1CIHN1bSAobmltIHN1bSBiYXNlIEIpIG9mIHR3byBub24tbmVnYXRpdmUgaW50ZWdlcnMgWCBhbmQgWSAod3JpdHRlbiBOaW1TdW0oQiwgWCwgWSkpIGlzIGNvbXB1dGVkIGFzIGZvbGxvd3M6PFwvcD5cclxuXHJcbjxwPldyaXRlIGVhY2ggb2YgWCBhbmQgWSBpbiBiYXNlIEIuPGJyIFwvPlxyXG5FYWNoIGRpZ2l0IGluIGJhc2UgQiBvZiB0aGUgTmltLUIgc3VtIGlzIHRoZSBzdW0gbW9kdWxvIEIgb2YgdGhlIGNvcnJlc3BvbmRpbmcgZGlnaXRzIGluIHRoZSBiYXNlIEIgcmVwcmVzZW50YXRpb24gb2YgWCBhbmQgWS48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGU6PFwvcD5cclxuXHJcbjxwcmU+XHJcbk5pbVN1bSgyLCAxMjMsIDQ1NikgPSAxMTExMDExICZjdXJyZW47IDExMTAwMTAwMCA9IDExMDExMDAxMSA9IDQzNVxyXG5OaW1TdW0oMywgMTIzLCA0NTYpID0gMTExMjAgJmN1cnJlbjsgMTIxMjIwID0gMTAyMDEwID0gMzAwXHJcbk5pbVN1bSg0LCAxMjMsIDQ1NikgPSAxMzIzICZjdXJyZW47IDEzMDIwID0gMTAzMDMgPSAzMDc8XC9wcmU+XHJcblxyXG48cD5UaGUgc3RyYXRlZ3kgZm9yIG5vcm1hbCBmb3JtIE5pbSBpcyB0byBjb21wdXRlIHRoZSBOaW0tMiBzdW0gVCBvZiB0aGUgc2l6ZXMgb2YgYWxsIHBpbGVzLiBJZiBhdCBhbnkgdGltZSwgeW91IGVuZCB5b3VyIHR1cm4gd2l0aCBUID0gMCwgeW91IGFyZSBndWFyYW50ZWVkIGEgV0lOLiBBbnkgb3Bwb25lbnQgbW92ZSBtdXN0IGxlYXZlIFQgbm90IDAgYW5kIHRoZXJlIGlzIGFsd2F5cyBhIG1vdmUgdG8gZ2V0IFQgYmFjayB0byAwLiBUaGlzIGlzIGRvbmUgYnkgY29tcHV0aW5nIE5pbVN1bSgyLCBULCBQUylmb3IgZWFjaCBwaWxlOyBpZiB0aGlzIGlzIGxlc3MgdGhhbiB0aGUgcGlsZSBzaXplIChQUyksIGNvbXB1dGUgdGhlIGRpZmZlcmVuY2UgYmV0d2VlbiB0aGUgUFMgYW5kIHRoZSBOaW0tMiBzdW0gYW5kIHJlbW92ZSBpdCBmcm9tIHRoYXQgcGlsZSBhcyB5b3VyIG5leHQgbW92ZS48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRvIGNvbXB1dGUgTmltU3VtKEIsIFgsIFkpLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBQLCAoMSAmbGU7IFAgJmxlOyAxMDAwKSwgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBkYXRhIHNldHMgdGhhdCBmb2xsb3cuIEVhY2ggZGF0YSBzZXQgaXMgYSBzaW5nbGUgbGluZSB0aGF0IGNvbnRhaW5zIHRoZSBkYXRhIHNldCBudW1iZXIsIGZvbGxvd2VkIGJ5IGEgc3BhY2UsIGZvbGxvd2VkIGJ5IHRocmVlIHNwYWNlIHNlcGFyYXRlZCBkZWNpbWFsIGludGVnZXJzLCBCLCBYIGFuZCBZLiAyICZsdDs9IEIgJmx0Oz0gMjAwMDAwMCwgMCAmbHQ7PSBYICZsdDs9IDIwMDAwMDAsIDAgJmx0Oz0gWSAmbHQ7PSAyMDAwMDAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGEgc2V0IHRoZXJlIGlzIG9uZSBsaW5lIG9mIG91dHB1dC4gSXQgY29udGFpbnMgdGhlIGRhdGEgc2V0IG51bWJlciBmb2xsb3dlZCBieSBhIHNpbmdsZSBzcGFjZSwgZm9sbG93ZWQgYnkgTiwgdGhlIGRlY2ltYWwgcmVwcmVzZW50YXRpb24gb2YgdGhlIE5pbSBzdW0gaW4gYmFzZSBCIG9mIFggYW5kIFkuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d