시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 56 39 38 70.370%

문제

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+XHJcblxyXG4iLCJpbnB1dCI6IlxyXG48cD5cclxuXHRcdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgVCAmbGU7IDEwMDApLCBcdWFkZjhcdWI5YWNcdWFjZTAgXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBCLCBYLCBZXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM4MTVcdWMyMThcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzQ0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWI0NTBcdWFjZTAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IEIgJmxlOyAyMDAwMDAwLCAwICZsZTsgWCAmbGU7IDIwMDAwMDAsIDAgJmxlOyBZICZsZTsgMjAwMDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBOaW1TdW0gKEIsIFgsIFkpXHVjNzU4IDEwXHVjOWM0XHVjMjE4IFx1ZDQ1Y1x1ZDYwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjY4NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik5pbS1CIFN1bSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGdhbWUgb2YgTklNIGlzIHBsYXllZCB3aXRoIGFueSBudW1iZXIgb2YgcGlsZXMgb2Ygb2JqZWN0cyB3aXRoIGFueSBudW1iZXIgb2Ygb2JqZWN0cyBpbiBlYWNoIHBpbGUuIEF0IGVhY2ggdHVybiwgYSBwbGF5ZXIgdGFrZXMgb25lIG9yIG1vcmUgKHVwIHRvIGFsbCkgb2JqZWN0cyBmcm9tIG9uZSBwaWxlLiBJbiB0aGUgbm9ybWFsIGZvcm0gb2YgdGhlIGdhbWUsIHRoZSBwbGF5ZXIgd2hvIHRha2VzIHRoZSBsYXN0IG9iamVjdCBpcyB0aGUgd2lubmVyLiBUaGVyZSBpcyBhIHdlbGwta25vd24gc3RyYXRlZ3kgZm9yIHRoaXMgZ2FtZSBiYXNlZCBvbiB0aGUgbmltLTIgc3VtLjxcL3A+XHJcblxyXG48cD5UaGUgTmltLUIgc3VtIChuaW0gc3VtIGJhc2UgQikgb2YgdHdvIG5vbi1uZWdhdGl2ZSBpbnRlZ2VycyBYIGFuZCBZICh3cml0dGVuIE5pbVN1bShCLCBYLCBZKSkgaXMgY29tcHV0ZWQgYXMgZm9sbG93czo8XC9wPlxyXG5cclxuPHA+V3JpdGUgZWFjaCBvZiBYIGFuZCBZIGluIGJhc2UgQi48YnIgXC8+XHJcbkVhY2ggZGlnaXQgaW4gYmFzZSBCIG9mIHRoZSBOaW0tQiBzdW0gaXMgdGhlIHN1bSBtb2R1bG8gQiBvZiB0aGUgY29ycmVzcG9uZGluZyBkaWdpdHMgaW4gdGhlIGJhc2UgQiByZXByZXNlbnRhdGlvbiBvZiBYIGFuZCBZLjxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZTo8XC9wPlxyXG5cclxuPHByZT5cclxuTmltU3VtKDIsIDEyMywgNDU2KSA9IDExMTEwMTEgJmN1cnJlbjsgMTExMDAxMDAwID0gMTEwMTEwMDExID0gNDM1XHJcbk5pbVN1bSgzLCAxMjMsIDQ1NikgPSAxMTEyMCAmY3VycmVuOyAxMjEyMjAgPSAxMDIwMTAgPSAzMDBcclxuTmltU3VtKDQsIDEyMywgNDU2KSA9IDEzMjMgJmN1cnJlbjsgMTMwMjAgPSAxMDMwMyA9IDMwNzxcL3ByZT5cclxuXHJcbjxwPlRoZSBzdHJhdGVneSBmb3Igbm9ybWFsIGZvcm0gTmltIGlzIHRvIGNvbXB1dGUgdGhlIE5pbS0yIHN1bSBUIG9mIHRoZSBzaXplcyBvZiBhbGwgcGlsZXMuIElmIGF0IGFueSB0aW1lLCB5b3UgZW5kIHlvdXIgdHVybiB3aXRoIFQgPSAwLCB5b3UgYXJlIGd1YXJhbnRlZWQgYSBXSU4uIEFueSBvcHBvbmVudCBtb3ZlIG11c3QgbGVhdmUgVCBub3QgMCBhbmQgdGhlcmUgaXMgYWx3YXlzIGEgbW92ZSB0byBnZXQgVCBiYWNrIHRvIDAuIFRoaXMgaXMgZG9uZSBieSBjb21wdXRpbmcgTmltU3VtKDIsIFQsIFBTKWZvciBlYWNoIHBpbGU7IGlmIHRoaXMgaXMgbGVzcyB0aGFuIHRoZSBwaWxlIHNpemUgKFBTKSwgY29tcHV0ZSB0aGUgZGlmZmVyZW5jZSBiZXR3ZWVuIHRoZSBQUyBhbmQgdGhlIE5pbS0yIHN1bSBhbmQgcmVtb3ZlIGl0IGZyb20gdGhhdCBwaWxlIGFzIHlvdXIgbmV4dCBtb3ZlLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdG8gY29tcHV0ZSBOaW1TdW0oQiwgWCwgWSkuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIFAsICgxICZsZTsgUCAmbGU7IDEwMDApLCB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIGRhdGEgc2V0cyB0aGF0IGZvbGxvdy4gRWFjaCBkYXRhIHNldCBpcyBhIHNpbmdsZSBsaW5lIHRoYXQgY29udGFpbnMgdGhlIGRhdGEgc2V0IG51bWJlciwgZm9sbG93ZWQgYnkgYSBzcGFjZSwgZm9sbG93ZWQgYnkgdGhyZWUgc3BhY2Ugc2VwYXJhdGVkIGRlY2ltYWwgaW50ZWdlcnMsIEIsIFggYW5kIFkuIDIgJmx0Oz0gQiAmbHQ7PSAyMDAwMDAwLCAwICZsdDs9IFggJmx0Oz0gMjAwMDAwMCwgMCAmbHQ7PSBZICZsdDs9IDIwMDAwMDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YSBzZXQgdGhlcmUgaXMgb25lIGxpbmUgb2Ygb3V0cHV0LiBJdCBjb250YWlucyB0aGUgZGF0YSBzZXQgbnVtYmVyIGZvbGxvd2VkIGJ5IGEgc2luZ2xlIHNwYWNlLCBmb2xsb3dlZCBieSBOLCB0aGUgZGVjaW1hbCByZXByZXNlbnRhdGlvbiBvZiB0aGUgTmltIHN1bSBpbiBiYXNlIEIgb2YgWCBhbmQgWS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=