Problem Statement

Let $S$ be the set of all positive integers.

Process $Q$ queries in order. The $i$-th query gives you an integer $A_i$ not less than $2$ and a positive integer $B_i$, so perform the following two steps in order.

1. Remove from $S$ all elements that are multiples of $A_i$.
2. Print the $B_i$-th smallest element of $S$. It can be shown that under the given constraints, $S$ contains at least $B_i$ elements at this point.

Constraints

• $1\le Q\le 10^5$
• $2\le A_i\le 10^9$
• $1\le B_i\le 10^5$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

Q
A_1 B_1
\vdots
A_Q B_Q

Output

Print $Q$ lines. The $i$-th line should contain the $B_i$-th smallest element of $S$ after removing all multiples of $A_i$ from $S$.