AT_arc197_c [ARC197C] Removal of Multiples

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.

The input is given from Standard Input in the following format: > $ Q $ $ A_1 $ $ B_1 $ $ \vdots $ $ A_Q $ $ B_Q $

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 $ .

### Sample Explanation 1 When the elements of $ S $ are listed in ascending order, the beginning of the list evolves as follows. - Initially, $ S=\lbrace 1,2,3,4,5,6,7,8,9,10,\ldots\rbrace $ . - The first query removes multiples of $ 5 $ , resulting in $ S=\lbrace1,2,3,4,6,7,8,9,11,12,\ldots\rbrace $ . - The second query removes multiples of $ 6 $ , resulting in $ S=\lbrace1,2,3,4,7,8,9,11,13,14,\ldots\rbrace $ . - The third query removes multiples of $ 6 $ , resulting in $ S=\lbrace1,2,3,4,7,8,9,11,13,14,\ldots\rbrace $ . - The fourth query removes multiples of $ 9 $ , resulting in $ S=\lbrace1,2,3,4,7,8,11,13,14,16,\ldots\rbrace $ . - The fifth query removes multiples of $ 123456789 $ , resulting in $ S=\lbrace1,2,3,4,7,8,11,13,14,16,\ldots\rbrace $ . ### 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.