CATS

Counter and Two Stacks (CATS) is an esoteric language built around a counter COUNTER and two stacks S1 and S2. Both stacks start as an infinite sequence of zeros.

PUSH inserts a value, POP removes the top, and ADD pops two values, adds them, and pushes the sum. If PUSH tries to insert a negative value, nothing is pushed; instead every element in that stack, including the infinite tail, has its least significant bit flipped ($X \oplus 1$).

Mr. Panda wanted the $X$-th multiple of $N$ strictly greater than $L$, but the buggy pseudocode below prints something else. You may assume $L$ is not a multiple of $N$.

COUNTER = X
WHILE COUNTER > 0
     S2 PUSH T1
     S1 POP
     FLIP LAST BINARY BIT OF ALL NUMBERS IN S1
     IF T2 > L
          COUNTER = COUNTER - 1
          IF COUNTER == 0 PRINT T2
     ELSE
          S2 PUSH N
          S2 PUSH N
          S2 ADD
          S2 ADD
          S1 PUSH T2
          S1 PUSH T2
          S2 POP
          S2 POP

T1 and T2 are the tops of S1 and S2. Inside the ELSE branch, S1 PUSH T2 uses T2 after the ADD steps. For each query, output the integer the pseudocode prints.

The first line contains $Q$, the number of queries.

Each of the next $Q$ lines contains three positive integers $X$, $L$, and $N$. The value $L$ is not a multiple of $N$.

For each query, print the integer produced by the pseudocode, one per line.

Model the infinite zero tail with one parity bit plus a finite prefix array. FLIP and negative PUSH xor 1 into the tail bit and every prefix cell. POP on an empty prefix leaves only the tail.