L. Function
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a positive integer $$$a$$$, we call a function $$$f: \mathbb {Z}^+\to\mathbb {Z}^+$$$ is good if and only if it satisfies:

  • $$$\forall x, f(f(x))=ax$$$;
  • $$$\forall x \lt y, f(x) \lt f(y)$$$.

Consider the smallest good function $$$g$$$ in lexicographical order, please calculate $$$g(x)$$$ for a given $$$x$$$.

Formally, the unique function $$$g$$$ with given $$$a$$$ satisfies:

  • $$$g$$$ is good.
  • For any good function $$$h$$$, there does not exist a positive integer $$$N$$$ satisfies $$$\forall i \lt N, g(i)=h(i)$$$ and $$$g(N) \gt h(N)$$$.
Input

The input contains several test cases, and the first line contains a positive integer $$$T$$$($$$1 \le T \le 10^5$$$) indicating the number of test cases.

For each test case, there is only one line containing two integers $$$a,x$$$ ($$$ 3 \le a \le 10^9,1 \le x \le 10^9$$$).

Output

For each test case, output one line with one integer $$$g(x)$$$.

Example
Input
5
3 1
3 2
3 3
4 5
11 4514
Output
2
3
6
12
16493