Ersel Nimgirmen is a proffessional nim player. He has wondered about similar games he can play using stones and came up with one.

In the new game, the game starts with a pile of \(\mathbf{N}\) stones. The first player takes an arbitrary number of stones that don't exceed \(\mathbf{N-1}\). In other turns, players can at most take \(\mathbf{M}\) times the number of stones that the other player took on the last turn. So, say that the first player takes \(\mathbf{K}\) stones, the second player can at most take \(\mathbf{K \cdot M}\) number of stones from the pile. The player who can not take any stones on their turn loses the game.

Assume that players always make the optimal moves. Can you find if Nimgirman can win the game he came up with?

Input

The first line contains the number of test cases \(\mathbf{T}\).

The next \(\mathbf{T}\) lines contain \(\mathbf{N}\) and \(\mathbf{M}\) for each test case.

• \(1 \leq \mathbf{T} \leq 50\)
• \(2 \leq \mathbf{N} \leq 10^{7}\)
• \(1 \leq \mathbf{M} \leq 10^{5}\)

Output

For each test case, if Nimgirmen loses, print "LOST". In other cases print the minimum number of stones he can take in the first turn.

Example

Input:

3
5 1
16 1
4 2

Output:

1
LOST
1

Input:

3
7 3
20 5
94 37

Output:

1
2
LOST

Explanation

Input 1

In the first case, Nimgirmen can win by starting with getting 1 or 2 stones. 1 is the smaller of these, so Nimgirmen starts with 1.

In the second case, he losts in all situations.

In the last case, he can only win by starting with getting 1 stone. There can be 2 situations after he plays his first move.

• His opponent takes 1 stone after his turn, in this case, he takes 2 stones.
• His opponent takes 2 stones after his turn, in this case, he takes 1 stone.

In both situations, his opponent can't make a move and loses.