시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 1 1 1 100.000%

문제

Young software developer Michael succeeded on Innopolis Open and was awarded by Innobook laptop with a pre-installed "Innome" web browser. This strange web browser can support at most $k$ open windows and the $i$-th open tab in the window uses $i$ megabytes of memory. Michael knows that his new laptop has $m$ megabytes of memory. Please help Michael to calculate the maximum number of tabs he can open.

입력

The first line contains single integer $t$, the number of tests. The next $t$ lines contains description of the tests one per line. Each test is represented by two integers $m$ and $k$,  the size of Innobook memory and the maximum possible number of windows.

출력

For each test output a single integer on a separate line, the maximum number of tabs that Michael can open.

서브태스크

번호 배점 제한
1 10

$t \le 100$, $m \le 10^6$, $k = 1$

2 10

$t \le 100$, $m \le 10^6$, $k \le 2$

3 20

$t \le 1000$, $m \le 10^9$, $k \le 10^9$

4 25

$t \le 10^5$, $m \le 10^9$, $k \le 10^9$

5 35

$t \le 10^5$, $m \le 10^{18}$, $k \le 10^9$

예제 입력 1

2
23 3
2 3

예제 출력 1

10
2

채점 및 기타 정보

  • 예제는 채점하지 않는다.