K Centers Selection Problem

In Ninja Land, there are cities numbered from 0 to N-1. The distances between each pair of cities are represented by an N * N matrix 'DIST', where 'DIST[i][j]' is the distance between city 'i' and city 'j'.

Ninja plans to install Coding Ninjas servers in K cities and needs to ensure that the maximum distance from any city to a nearest server is as small as possible.

Input:

The first line contains an integer T, the number of test cases.
Each test case starts with two integers N and K, where N is the number of cities, and K is the number of server installations.
The next N lines contain N integers each, representing the matrix 'DIST'.

Output:

For each test case, output a single integer representing the optimized maximum distance of any city from the nearest server.

Example:

Input:

T = 1
N = 4, K = 2
DIST =
[0, 10, 7, 6]
[10, 0, 8, 5]
[7, 8, 0, 12]
[6, 5, 12, 0]

Output:

6

Explanation:

Choose cities 2 and 3 for the server installation. The maximum minimized distance is 6.

Constraints:

• 1 ≤ T ≤ 50
• 1 ≤ N ≤ 15
• 1 ≤ K ≤ N
• 1 ≤ DIST[i][j] ≤ 109, for i ≠ j
• DIST[i][j] = 0, for i = j

Note:

It is not necessary to print the output; just implement the function as required.