## SQRMINSUM - Minimum Sum

Suppose you have a list of integers, and a move is defined as taking one of the integers from the list and replacing it with its square root, rounded down to the nearest integer.

Given an integer l and an integer k, start with the array [1, 2, 3 ... l] and find the minimal sum of the array after k moves.

### Example

For l = 5 and k = 2, the output should be squareRoots(l, k) = 10.

After square rooting 5 to get [1, 2, 3, 4, 2] and then square rooting 3 to get[1, 2, 1, 4, 2], we end up with a sum of 10.

1 ≤ l ≤ 104

1 ≤ k ≤ 104

T=10000

### Input

The first line contains T the number of test cases followed by 2*T lines containing l and k.

### Output

For every test case, output one line containing an integer, i.e. the minimal possible sum.

### Sample

```Input:
2
5
2
2327
4895

Output:
10
10647```

 Added by: Piyush Kumar Date: 2016-06-10 Time limit: 5s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: C CSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG C99 JAVA PYTHON PYPY PYTHON3 Resource: Standard Pro Co