#include <bits/stdc++.h>
#define int long long int
#define double long double
#define endl '\n'
#define all(c) c.begin(),c.end()
#define mp(x,y) make_pair(x,y)
#define eb emplace_back
#define tr(k,st,en) for(int k = st; k <= en ; k++)
#define trb(k,en,st) for(int k = en; k >= st ; k--)
#define test int TN; cin>>TN; tr(T,1,TN)
#define mxe(c) max_element(all(c))
#define mne(c) min_element(all(c))
using namespace std;

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template < typename T_container, typename T = typename enable_if < !is_same<T_container, string>::value, typename T_container::value_type >::type > ostream & operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }

#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

typedef pair<int, int> pr;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pr> vpr;

//const int mod = 1e9+7;
const int inf = 9e18;

struct Pt {
    int x, y;
    Pt(int _x, int _y) : x(_x), y(_y) {}
    Pt operator - (Pt b) {
        return Pt(x - b.x, y - b.y);
    }
    int isRight(Pt a, Pt b) {
        Pt p = *this - a;
        Pt q = b - a;
        int l = p.x * q.y - p.y * q.x;
        if (l > 0) return 1;
        if (l < 0) return -1;
        return 0;
    }
};

bool Intersect(Pt a, Pt b, Pt c, Pt d) {
    int l1, l2, l3; l1 = l2 = 0; l3 = 1;
    if (a.isRight(c, d) * b.isRight(c, d) <= 0) l1 = 1;
    if (c.isRight(a, b) * d.isRight(a, b) <= 0) l2 = 1;
    if (max(a.x, b.x) < min(c.x, d.x) or max(a.y, b.y) < min(c.y, d.y) or
            max(c.x, d.x) < min(a.x, b.x) or max(c.y, d.y) < min(a.y, b.y) ) l3 = 0;
    return l1 and l2 and l3;
}
typedef pair<pair<Pt, Pt>, int> prt;

int solve(vector<prt> in, int k) {
    int n = in.size();
    sort(all(in), [] (prt a, prt b) {
        return a.second < b.second;
    });
    int l = 0, r = 0;
    int ans = inf;
    vi tmp(n + 1, 0);
    int cur = 0;
    while (l < n) {
        while (r < n) {
            if (cur >= k) {
                break;
            }
            for (int i = l; i < r; i++) {
                if (Intersect(in[i].first.first, in[i].first.second, in[r].first.first, in[r].first.second)) {
                    tmp[i]++;
                    cur++;
                }
            }
            r++;

        }
        if (cur >= k) {
            ans = min(ans, in[r - 1].second - in[l].second);
        }
        cur -= tmp[l];
        l++;
    }
    return ans == inf ? -1 : ans;
}

void func() {
    int t;
    cin >> t;
    tr(i, 1, t) {
        int n, k ;
        cin >> n >> k;
        vector<prt> in;
        tr(i, 1, n) {
            int x1, y1, x2, y2, c ;
            cin >> x1 >> y1 >> x2 >> y2 >> c;
            in.eb(mp(Pt(x1, y1), Pt(x2, y2)), c);
        }
        int s = solve(in, k);
        cout  << s << endl;
    }
}

int32_t main() {
    std::ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
//    cout<<"----START-----"<<endl;
    func();
    return 0;
}