AT_arc197_c [ARC197C] Removal of Multiples

すべての正整数からなる集合 $ S $ があります． $ Q $ 個のクエリを順に処理してください． $ i $ 番目のクエリでは， $ 2 $ 以上の整数 $ A_i $ および，正整数 $ B_i $ が与えられるので，次の $ 2 $ つのことを順に行ってください． 1. $ S $ から $ A_i $ の倍数である要素をすべて削除する． 2. $ S $ の要素のうち小さい方から $ B_i $ 番目のものを出力する．なお本問の制約のもとで， $ S $ はこの時点で $ B_i $ 個以上の要素を含むことが証明できる．

入力は以下の形式で標準入力から与えられます． > $ Q $ $ A_1 $ $ B_1 $ $ \vdots $ $ A_Q $ $ B_Q $

$ Q $ 行出力してください． $ i $ 行目には $ i $ 番目のクエリにおいて， $ S $ から $ A_i $ の倍数である要素をすべて削除した後の， $ S $ の要素のうち小さい方から $ B_i $ 番目のものを出力してください．

### Sample Explanation 1 $ S $ の要素を昇順に並べたときの先頭に近い部分がどうなるかを説明します． - 初期状態では， $ S=\lbrace 1,2,3,4,5,6,7,8,9,10,\ldots\rbrace $ です． - $ 1 $ 番目のクエリでは $ 5 $ の倍数を削除して， $ S=\lbrace1,2,3,4,6,7,8,9,11,12,\ldots\rbrace $ となります． - $ 2 $ 番目のクエリでは $ 6 $ の倍数を削除して， $ S=\lbrace1,2,3,4,7,8,9,11,13,14,\ldots\rbrace $ となります． - $ 3 $ 番目のクエリでは $ 6 $ の倍数を削除して， $ S=\lbrace1,2,3,4,7,8,9,11,13,14,\ldots\rbrace $ となります． - $ 4 $ 番目のクエリでは $ 9 $ の倍数を削除して， $ S=\lbrace1,2,3,4,7,8,11,13,14,16,\ldots\rbrace $ となります． - $ 5 $ 番目のクエリでは $ 123456789 $ の倍数を削除して， $ S=\lbrace1,2,3,4,7,8,11,13,14,16,\ldots\rbrace $ となります． ### Constraints - $ 1\leq Q\leq 10^5 $ - $ 2\leq A_i\leq 10^9 $ - $ 1\leq B_i\leq 10^5 $ - 入力される値はすべて整数