删除倍数

时间限制：4s
空间限制：1024MB

题目描述

集合 $S$ 初始包含所有正整数。依次处理 $Q$ 次询问：给定 $A_i\ge2$ 和正整数 $B_i$，先从 $S$ 中删除所有 $A_i$ 的倍数，再输出 $S$ 中第 $B_i$ 小的元素。保证答案存在。

输入格式

第一行一个整数 $Q$，接下来 $Q$ 行每行两个整数 $A_i,B_i$。

输出格式

每次询问输出一行答案。

样例输入 1

5
5 10
6 1
6 10
9 10
123456789 111

样例输出 1

12
1
14
16
178

数据范围

对于所有数据，$1\le Q\le10^5$，$2\le A_i\le10^9$，$1\le B_i\le10^5$。