// Author:   old_school
// Created:  16.01.2021 17:30:16

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,fma") 
#pragma GCC optimization ("unroll-loops")
using namespace std;
#define lld               long long int
#define ld                long double
#define pb                push_back
#define ppb               pop_back 
#define mp                make_pair
#define F                 first
#define S                 second
#define nl                '\n'
#define all(c)            (c).begin(),(c).end()
#define rall(c)           (c).rbegin(),(c).rend()
#define sz(c)             (c).size()
#define tr(x,a)           for(auto &a : x)
#define psnt(x,a)         (x).find(a)!=(x).end()
#define vpsnt(x,a)        find(all(x),a)!=(x).end()
#define MOD               1000000007
#define tod               1
#define pi                3.1415926536
#define itr(i,a,b)        for(lld i=a;i<=b;i++)
#define itrn(i,a,b)       for(lld i=a;i>=b;i--)
#define iot(n)            for(lld i=0;i<n;i++)
#define pls(n,arr)        lld arr[n]; iot(n)  cin>>arr[i];
#define bye               fflush(stdout)

typedef pair<lld,lld>     pii;
typedef pair<string,lld>  psi;

template <typename T>
bool mycomp(T x,T y){ 
   return (x==y);  //give your condition here
}
bool paircomp(const pair<lld,lld> &x,const pair<lld,lld> &y){ 
return x.second<y.second;
}

void solve(){
   lld n,k; cin>>n>>k;
   lld hash[n+5]={0};
   pls(n,a);
   itr(i,0,n-1) hash[a[i]]++;
   lld sumr=0;
   lld z=k,i=0;
   while(z!=0&&i<n){
   	  if(hash[i]>=z) ;
   	  else{
   	  	sumr+=(z-hash[i])*i;
   	  	z=hash[i];
   	  }
   	  i++;
   }
   cout<<sumr;
}
int main(){
       ios_base::sync_with_stdio(false);
             cin.tie(0);
            cout.tie(0);
      lld t=1; //cin>>t;  
      while(t--){
            solve();
            cout<<endl;
      }
}


#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>
#include <cassert>
#include <cmath>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <cstdlib>

using namespace std;

#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define li long long
#define pii pair<int, int>
#define vi vector<int>
#define li long long

#define forn(i, n) for (int i = 0; i < (int)n; i++)
#define fore(i, b, e) for (int i = (int)b; i <= (int)e; i++)

int main() {
	int tests;
	scanf("%d", &tests);
	forn(test, tests) {
		int l, r;
		scanf("%d%d", &l, &r);
		li ans = 0;
		if (2 * l <= r) {
			li len = r - 2 * l + 1;
			ans = len * (len + 1) / 2;
		}
		cout << ans << endl;
	}
}