시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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


## 채점 및 기타 정보

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