Şehmettin is an old friend of Zeyna and a con artist. He finds unlosable games, perfects his technique then tricks people into playing his game with promises of making money. The current game he is playing works like this:

• Each turn the current player will take at least 1 and at most \(\mathbf{\dfrac{X(K-1)}{K}}\) balls from the table (Assume \(\mathbf{X}\) is the current number of balls on the table.).
  • The player can always take 1 ball as long as there is at least 1 ball on the table.
• The player who gets the last ball wins.

Zeyna being the righteous and genius mathematician she is, decided to end his old friend Şehmettin's evil ways. After countless days of hard work Zeyna found out that for some number of balls Şehmettin can not win (assuming that both players play the game perfectly), lets's call this number lossNUM. She believes that she has created an algorithm that finds every lossNUM there is. To confirm her algorithm works Zeyna asks you, a known gamer, for help so that she can be sure of her algorithm and win against evil Şehmettin. Help her by giving her \(\mathbf{N_i}\)'th smallest lossNUM for given \(\mathbf{K_i}\) value whenever she asks you to.

• Şehmettin always starts the game
• A player can not take a fractional number of balls in a turn.
• Since this number can be quite big, write modulo 1000000007 of the number*

Input

The first line contains 1 integer: the number of queries.

• \(1\leq\mathbf{q}\leq 10^4\)

Next \(\mathbf{q}\) lines contain 2 integers each:

• \(1\leq\mathbf{N_i}\leq 10^6\) (queried lossNUM index for the given \(\mathbf{K_i}\))
• \(2\leq\mathbf{K_i}\leq 10^6\)

Output

Output contains \(\mathbf{q}\) integers:

• Print the \(\mathbf{N_i}\)'th lowest losing number (modulo 1000000007) for given \(\mathbf{K_i}\) values.

Example

Input

2
1 2
3 3

Output

2 22

Explanation

This is the explanation for 1 2 case:

• If there is 1 ball on the table at the start of the game, player 1 takes it and wins. So the 1'st lowest losing number must be higher than 1.
• If there are 2 balls on the table at the start of the game, player 1 will have to take 1 ball and the 2nd player wins by getting the remaining ball. So the 1'st lowest losing number must be 2.