Một coder trẻ với mật danh Hecker đã chiến thắng giải đấu Surajet Open giành được chiếc laptop Surajook độc quyền của nhà tài trợ Suraj.

Chiếc laptop này có cài đặt sẵn một trình duyệt internet do công ty Suraj phát triển với các thử nghiệm hết sức độc đáo. Tuy nhiên trình duyệt bị giới hạn khi chỉ có thể mở được nhiều nhất \(k\) cửa sổ và tab thứ \(i\) trong mỗi cửa sổ chiếm \(i\) megabytes trong bộ nhớ. Hecker cho biết chiếc laptop mới có \(m\) megabytes bộ nhớ dành cho trình duyệt.

Yêu cầu: Hãy giúp Hecker tính xem cậu ta có thể mở được nhiều nhất là bao nhiêu tab.

Input

• Dòng đầu tiên chứa số nguyên dương \(T (1 ≤ T ≤ 10^5)\) là số bộ test;

• T dòng tiếp theo: mỗi dòng chứa 2 nguyên dương \(m, k (1 ≤ m ≤ 10^{18}, 1 ≤ k ≤ 10^9);\)

Các số trên cùng một dòng được ghi cách nhau một dấu cách.

Output

• Gồm T dòng: Mỗi dòng ghi một số nguyên duy nhất là số tab nhiều nhất mà Hecker có thể mở tương ứng với mỗi test.

Ràng buộc:

• Có 50% số test ứng với 50% số điểm thoả mãn: \(T≤ 2×10^3; \)

• Có 50% số test còn lại ứng với 50% số điểm thoả mãn: \(T≤10^5.\)

Sample Input

2
23 3
2 3

Sample Output

10
2