On a table, there are n apples, the i-th apple has the weight k + i (1 ≤ i ≤ n). Exactly one of the apples is sweet, lighter apples are all bitter, while heavier apples are all sour. The giant wants to know which one is sweet, the only thing he can do is to eat apples. He hates bitter apples and sour apples, what should he do? For examples, n = 4, k = 0, the apples are of weight 1, 2, 3, 4. The giant can first eat apple #2. • if #2 is sweet, the answer is #2 • if #2 is sour, the answer is #1 • if #2 is bitter, the answer might be #3 or #4, then he eats #3, he’ll know the answer regardless of the taste of #3 The poor giant should be prepared to eat some bad apples in order to know which one is sweet. Let’s compute the total weight of apples he must eat in all cases. • #1 is sweet: 2 • #2 is sweet: 2 • #3 is sweet: 2 + 3 = 5 • #4 is sweet: 2 + 3 = 5 The total weights = 2 + 2 + 5 + 5 = 14. This is not optimal. If he eats apple #1, then he eats total weight of 1, 3, 3, 3 when apple #1, #2, #3 and #4 are sweet respectively. This yields a solution of 1 + 3 + 3 + 3 = 13, beating 14. What is the minimal total weight of apples in all cases? Input The first line of input contains a single integer t (1 ≤ t ≤ 100), the number of test cases. The following t lines each contains a positive integer n and a non-negative k (1 ≤ n + k ≤ 500). Output For each test case, output the minimal total weight in all cases as shown in the sample output. Sample Input 5 20 30 40 50 10 20
2/2 Sample Output Case 1: 2 Case 2: 6 Case 3: 13 Case 4: 22 Case 5: 605