Nim 합

Nim 게임은 여러 개의 돌무더기를 놓고 진행하는 게임이다. 각 차례에 플레이어는 돌무더기 하나를 골라 1개 이상, 그 무더기 전체 이하의 돌을 가져간다. 일반적인 Nim 게임에서는 마지막 돌을 가져가는 사람이 이긴다. 이 게임의 대표적인 전략은 Nim-2-sum을 이용한다.

FoodVictory에 신제품 algo90을 납품하던 용태는 물류 관리자 영우의 계속되는 횡포를 견디지 못하고 대결을 신청했다. 영우는 자신 있는 Nim 게임을 종목으로 골랐고, 용태는 Nim 게임의 전략을 찾아보았다.

두 음이 아닌 정수 X와 Y의 Nim-B-sum, 즉 B진법 Nim 합을 NimSum(B, X, Y)라고 하자. 이 값은 다음 절차로 계산한다.

1. X와 Y를 B진법으로 나타낸다.
2. 각 자리에서 X의 자리수와 Y의 자리수를 더한 뒤, 그 합을 B로 나눈 나머지를 결과의 해당 자리수로 둔다.

계산 예시는 다음과 같다.

• NimSum(2, 123, 456) = 1111011 ¤ 111001000 = 110110011 = 435
• NimSum(3, 123, 456) = 11120 ¤ 121220 = 102010 = 300
• NimSum(4, 123, 456) = 1323 ¤ 13020 = 10303 = 307

일반적인 Nim 게임에서는 모든 돌무더기 크기에 대해 Nim-2-sum T를 계산한다. 용태가 자신의 차례를 마칠 때마다 T가 0이 되도록 만들 수 있다면 반드시 이길 수 있다. 영우가 T가 0이 아닌 상태를 남겨도, 항상 다시 T를 0으로 만드는 방법이 존재한다. 각 무더기의 돌 수를 PS라고 할 때 NimSum(2, T, PS)를 계산하고, 그 값이 PS보다 작다면 PS와 그 값의 차이만큼 돌을 가져가면 된다.

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진수로 출력한다.