#include <bits/stdc++.h>
using namespace std;
 
#define pr pair<int,int>
#define f first
#define s second
 
bool compare(pr a, pr b){
	return a.s<b.s;
}
 
int solver(vector<int> x ,vector<int> y, int k){
	int n = x.size();
	int minArea = INT_MAX;
	// generate points
    vector<pr> xsort, ysort;
 
    for (int i = 0; i < n; ++i) {
        xsort.push_back({x[i],y[i]});
        ysort.push_back({x[i],y[i]});
    }
 
    // sort points by X
    sort(xsort.begin(), xsort.end());
 
    // sort points by Y
    sort(ysort.begin(), ysort.end(), compare);
 
    for (int i = 0; i < n - k + 1; ++i) {
        for (int j = 0; j < n - k + 1; ++j) {
        	pr lp = xsort[i];
        	pr bp = ysort[j];
 
            if (lp.f > bp.f || lp.s < bp.s) {
                continue;
            }
 
            int leftEdge = lp.f - 1;
            int bottomEdge = bp.s - 1;
 
            set<pr> tempPoints, acceptablePoints;
            for(int m =i; m<n; m++)
            	tempPoints.insert(xsort[m]);
 
            for(int m=j; m<n; m++){
            	if(tempPoints.count(ysort[m])){
            		acceptablePoints.insert(ysort[m]);
            	}
            }
 
            if (acceptablePoints.size() < k) {
                continue; // not enough points
            }
 
            // calculate and sort areas
            vector<int> areas;
 
            for (auto point : acceptablePoints) {
                int sqside = max(point.f + 1 - leftEdge, point.s + 1 - bottomEdge);
                areas.push_back(sqside * sqside);
            }
 
            sort(areas.begin(), areas.end());
 
            int currentArea = areas[k - 1];
            if (minArea > currentArea) {
                minArea = currentArea;
            }
        }
    }
    return minArea ;
}
 
int main() {
	int t; cin>>t;
	while(t--){
		int N;
	    int K;
	    cin>>N>>K;
	    vector<int> x(N), y(N);
 
		for (int i = 0; i < N; ++i) {
	        cin>>x[i]>>y[i];
		}
 
	    cout<<solver(x,y,K)<<endl;
	}
	return 0;
}