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$