시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 53 36 35 68.627%

문제

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진수 표현을 출력한다.

예제 입력

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

예제 출력

435
300
307
429

힌트