B	Anti Arithmetic Sequence
	Input: Standard Input Output: Standard Output

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*10⁹) and p (3≤p≤30).

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 Output for Sample Input

3 10 3 10 5 100 7

29 12 130

---

Problemsetter: Abdullah al Mahmood

Special Thanks: Derek Kisman