Nim Sum

Nim is a game played with several piles of stones. On each turn, a player chooses one pile and removes at least one stone, up to the entire pile. In the usual version of Nim, the player who takes the last stone wins. A standard strategy for this game uses the Nim-2-sum.

Yongtae was supplying FoodVictory with the new product algo90, but after enduring repeated pressure from the logistics manager Youngwoo, he challenged Youngwoo to a match. Youngwoo chose Nim, his strongest game, and Yongtae looked up the strategy.

For two nonnegative integers X and Y, define their Nim-B-sum, the base-B Nim sum, as NimSum(B, X, Y). It is computed as follows.

1. Write X and Y in base B.
2. For each digit position, add the digit of X and the digit of Y, then take the remainder modulo B. That remainder becomes the digit of the result at the same position.

The following calculations illustrate the definition.

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

In ordinary Nim, compute the Nim-2-sum T of all pile sizes. If Yongtae can always finish his turn with T equal to 0, he is guaranteed to win. Even if Youngwoo leaves T nonzero, there is always a move that makes T zero again. For each pile size PS, compute NimSum(2, T, PS). If that value is smaller than PS, remove the difference between PS and that value from the pile.

Computing NimSum by hand is tedious. Write a program that computes NimSum(B, X, Y) for Yongtae.

The first line contains the number of test cases T. (1 <= T <= 1000)

Each test case consists of one line containing three integers B, X, and Y separated by spaces. (2 <= B <= 2000000, 0 <= X <= 2000000, 0 <= Y <= 2000000)

For each test case, print the decimal representation of NimSum(B, X, Y).