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.

We start with [1, 2, 3, 4, 5].

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.

Constraints

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:All except: ASM64 GOSU JS-MONKEY
Resource:Standard Pro Co

hide comments
2016-06-17 01:33:29
U have given time limit 5second then how a soln of O(klog(l)) give tle..?
even if constraints of k and l are not so large..

Re: Look at the number of test cases, It is 10^4. 10^4*(your calculations with each test case) will time out!

Last edit: 2016-06-17 06:21:44
2016-06-14 15:06:49 Piyush Kumar
@Bhuvanesh, i have updated that number of test cases=10000, and k<=10000, and l<=10000. Given your complexity, your number of calculations will be in the order of 10^9 which will time out. You need to do better with the complexity. Also, think about doing some pre computation.
2016-06-14 14:30:10
Awesome sum! , AC in one go!

Last edit: 2016-06-14 14:30:20
2016-06-14 06:06:56 Bhuvnesh Jain
@Piyush, what is the expected time complexity? Mine is O(k log(l)), which is giving TLE, with and without fast I/O.

Edit: Thanks for the update, Solved it, trying for reducing the time and reaching the expected solution. Nice problem :)

Re: Glad you liked it :)

Last edit: 2016-06-16 12:42:24
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.