В городе инженеров каждый секретный код собирают из степеней одного числа. Для выбранного основания n код считается допустимым, если его можно представить в виде суммы различных степеней числа n:

n^0, n^1, n^2, ...

При этом каждую степень можно использовать не более одного раза.

Например, при n = 3 допустимыми будут числа:

• 1 = 3^0
• 3 = 3^1
• 4 = 3^0 + 3^1
• 9 = 3^2
• 10 = 3^0 + 3^2

Если выписать все допустимые коды в порядке возрастания, то для каждого запроса нужно определить код с номером k.

Формат входных данных

В первой строке записано целое число t — количество запросов.

В каждой из следующих t строк записаны два целых числа n и k:

• 2 <= n <= 10^9
• 1 <= k <= 10^9

Формат выходных данных

Для каждого запроса выведите k-й допустимый код по модулю 10^9 + 7.

Примечание

Допустимые коды удобно нумеровать с 1.

Например, при n = 2 последовательность допустимых кодов начинается так:

1, 2, 3, 4, 5, 6, 7, 8, ...

А при n = 3:

1, 3, 4, 9, 10, 12, 13, 27, ...

Пример

Входные данные

3
3 1
3 2
3 5

Выходные данные

1
3
10

Пояснение к примеру

Для n = 3 допустимые коды по возрастанию:

1, 3, 4, 9, 10, 12, 13, ...

• 1-й код — 1
• 2-й код — 3
• 5-й код — 10