You are given two integers \(N\) and \(K\) denoting the number of elements in the array and an arbitrary integer respectively. You can perform the following operations:

1. Select an index \(i\).
2. Delete the \(i^{th}\) element.
3. Delete \(K\) elements to the left of it if they exist or you can delete all the elements if the number of elements to the left of it is less than \(K\).
4. Delete \(K\) elements to the right of it if they exist or you can delete all if the number of elements to the right of it is less than \(K\).

Your task is to delete all the elements of the array using the minimum number of provided operations.

Input format

• The first line contains an integer \(T\) denoting the number of test cases.
• The first line of each test case contains a single line containing two space-separated integers \(N\) and \(K\).

Output format

Print \(i^{th}\) \(T\) lines denoting the answer to the \(i^{th}\) test case.

Constraints

\( 1\leq T \leq 20000\)

\(1 \leq N,K \leq 1e9\)