Let \(\oplus\) denote the bitwise XOR and \(\text{mod}\) denote the modulo operation. The condition can be written as \(X\oplus N = X\ \text{mod}\ N\).

If \(X < N\), then \(X \oplus N = X \ \text{mod}\ N = X\) implies \(N=0\), which is improper. Therefore, we assume \(X \geq N\).

By considering bits, we find that \(X \oplus N \geq X - N\). From this, we get the inequality \(X\ \text{mod}\ N\geq X-N\).

Let \(X_1\) be the quotient and \(X_2\) the remainder when \(X\) is divided by \(N\), so \(X = X_1 N + X_2\). The above inequality becomes \(X_2\geq (X_1-1)N+X_2\), and by rearranging, we see \(X_1 \le 1\). Combined with \(X \geq N\), it follows that \(X_1 = 1\). Equivalently, \(N \le X < 2N\). From here on, we work under the condition \(N \le X < 2N\).

Since \(N \le X < 2N\), we have \(X \ \text{mod}\ N = X - N\). The original condition then becomes \(X \oplus N = X - N\). Analyzing the bitwise subtraction and the bitwise XOR, they differ in behavior only in the following case:

• The \(k\)-th bit of \(X\) is \(0\), and the \(k\)-th bit of \(N\) is \(1\). … \((\star)\)

Specifically, if \((\star)\) happens for some bit \(k\), then \(X \oplus N\) becomes larger by \(2^{k+1}\) compared to \(X - N\).

Hence, \(X \oplus N = X - N\) holds if and only if there is no \(k\) satisfying \((\star)\). This is equivalent to saying that \(X\) “contains” all bits of \(N\). In other words, for every bit position where \(N\) has a \(1\), \(X\) also has a \(1\).

Summarizing, the necessary and sufficient conditions for \(X\) to be compatible with \(N\) are:

1. \(N \le X < 2N\) … \((\text{A})\)
2. \(X\) contains all bits of \(N\) … \((\text{B})\)

Finally, we want to find the \(K\)-th smallest number \(X\) that is compatible with \(N\).

Looking at condition \((\text{B})\): if the \(k\)-th bit of \(N\) is \(1\), then the \(k\)-th bit of \(X\) must be \(1\). If the \(k\)-th bit of \(N\) is \(0\), there is no restriction for \(X\) at that bit. Therefore, we take all bit positions where \(N\) is \(0\), and fill them with the binary representation of \(K-1\) in order from lower to higher bits. That gives the \(K\)-th smallest such \(X\). If that \(X\) does not satisfy \((\text{A})\), then the answer is -1.

This solves the problem. The complexity is \(O(\log N)\) per test case.

Sample Implementation (Python3)

for _ in range(int(input())):
    n, k = map(int, input().split())
    k -= 1
    x = n
    z = 0
    for i in range(30):
        while n & (1 << z):
            z += 1
        if k & (1 << i):
            x |= 1 << z
        z += 1
    print(x if x < 2 * n else -1)