B'In the summer, Vika likes to visit her country house. There is everything for relaxation: comfortable swings, bicycles, and a river. There is a wooden bridge over the river, consisting of n planks. It is quite old and unattractive, so Vika decided to paint it. And in the shed, they just found cans of paint of k colors. After painting each plank in one of k colors, Vika was about to go swinging to take a break from work. However, she realized that the house was on the other side of the river, and the paint had not yet completely dried, so she could not walk on the bridge yet. In order not to spoil the appearance of the bridge, Vika decided that she would still walk on it, but only stepping on planks of the same color. Otherwise, a small layer of paint on her sole will spoil the plank of another color. Vika also has a little paint left, but it will only be enough to repaint one plank of the bridge. Now Vika is standing on the ground in front of the first plank. To walk across the bridge, she will choose some planks of the same color (after repainting), which have numbers 1 <= i_1 < i_2 < ldots < i_m <= n (planks are numbered from 1 from left to right). Then Vika will have to cross i_1 - 1, i_2 - i_1 - 1, i_3 - i_2 - 1, ldots, i_m - i_{m-1} - 1, n - i_m planks as a result of each of m + 1 steps. Since Vika is afraid of falling, she does not want to take too long steps. Help her and tell her the minimum possible maximum number of planks she will have to cross in one step, if she can repaint one (or zero) plank a different color while crossing the bridge. Each test consists of multiple test cases. The first line contains a single integer t ( 1 <= t <= 10^4 ) -- the number of test cases. The description of the test cases follows. The first line of each test case contains two integers n and k ( 1 <= k <= n <= 2 cdot 10^5 ) -- the number of planks in the bridge and the number of diff'...