Lộc muốn rủ bạn bè sang nhà mình chơi một trò chơi mà ở đó mọi người ngồi vào một cái bàn tròn (trò này rất phổ biến mỗi dịp tết đến xuân về). Bàn tròn đó có \(n\) chỗ, và mỗi người cảm thấy thoải mái nhất khi nếu tổng số ghế trống bên trái và bên phải không ít hơn \(k\). Lộc muốn mời tối đa số bạn để mỗi người đều cảm thấy thoải mái.

Bạn hãy giúp Lộc xác định số người tối đa được mời.

Input

• Dòng đầu tiên chứa số \(T\) (\(1 \le T \le 1000\)) là số bộ test.
• \(T\) dòng tiếp theo, mỗi dòng chứa hai số tự nhiên \(n, k\).

Output

• Với mỗi test, đưa ra một số nguyên duy nhất là số người bạn tối đa có thể được mời.

Constraints

• \(3 \le n \le 10^{18}\)
• \(1 \le k \le n - 1\)

Example

1
6 1

4