An anti-arithmetic sequence is one in which no subsequence of length p does form an arithmetic sequence. An arithmetic sequence is a sequence of numbers such that the difference of any two successive members of the sequence is a constant. For instance, the sequence 3, 5, 7, 9, 11, 13 . . . is an arithmetic progression with common difference 2. Now for a given p an infinite anti-arithmetic sequence is built in the following way. • The sequence will contain only positive numbers and strictly increasing. • The first p−1 numbers of the sequence is 1, 2, . . . , p−1. After that each time the smallest number is added to the sequence so that no subsequence of length p forms an arithmetic sequence. For p = 3 the infinite sequence is 1, 2 , 4, 5, 10, 11, 13, 14, 28, 29 and so on. Your task is to given p and n find the nth value of the anti-arithmetic sequence. Input First line of the input contains an integer T (1 ≤ T ≤ 1000) which denotes the number of test cases. Then each of the following T lines contains one test case. Each case contains 2 integers n (1 ≤ n ≤ 2 ∗ 1010) and p (3 ≤ p ≤ 30), and p is always a prime number. Output For each test case output contains 1 number indicating the nth value of the anti arithmetic sequence of p. This value will always fit into 64-bit signed integer. Sample Input 3 10 3 10 5 100 7 Sample Output 29 12 130