Innome

Time limit2sMemory limit512 MB

Summary

Given memory m and at most k windows, where the i-th tab in a window costs i megabytes, find the maximum total number of tabs.

Level: Medium5 of 10
Topics: Math, Binary search, Greedy, Implementation
Solved: No attempts yet

Problem

Young software developer Michael succeeded at Innopolis Open and was awarded an 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 a window uses $i$ megabytes of memory. Michael knows that his new laptop has $m$ megabytes of memory. Help Michael calculate the maximum number of tabs he can open.

Input

The first line contains a single integer $t$ , the number of tests. The next $t$ lines contain descriptions 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.

Output

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

Examples1

Example 1
Input
```
2
23 3
2 3
```
Expected output
```
10
2
```