SURAJ

Time limit: 1.0s , Memory limit: 256M , Points: 100

Một coder trẻ với mật danh Hecker đã chiến thắng giải đấu Surajet Open và 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$ ~k~ cửa sổ và tab thứ $i$ ~i~ trong mỗi cửa sổ chiếm $i$ ~i~ megabytes trong bộ nhớ. Hecker cho biết chiếc laptop mới có bộ nhớ $m$ ~m~ megabytes. Bạn 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 gồm một số nguyên $T$ ~T~ $(1 \le T \le 10^5)$ ~(1 \le T \le 10^5)~.
Dòng thứ $i + 1$ ~i + 1~ $(1 \le i \le T)$ ~(1 \le i \le T)~ gồm hai số nguyên $m, k$ ~m, k~ $(1 \le m \le 10^{18},$ ~(1 \le m \le 10^{18},~ $1 \le k \le 10^9)$ ~1 \le k \le 10^9)~ là tổng bộ nhớ của Surajook và số cửa sổ nhiều nhất có thể mở.