Gotta Catch 'Em All

Ash Ketchum is a Pokemon trainer who wants to catch every Pokemon in the world. He has caught most of them and needs K more different types to complete his set.

Ash lives in a 2D grid world. Pokemons spawn at integer coordinates, and several Pokemons can share the same type. Ash needs K different types, not any K Pokemons.

Ash throws a large square net from the sky. A Pokemon is caught if it lies inside the net or on one of its edges. Each side of the square is parallel to the x-axis or the y-axis. Find the minimum side length of a square that contains Pokemons of K different types. The net must have positive area, so the side must be positive.

The first line contains a single integer T, the number of test cases ($1 \le T \le 100$).

Each test case starts with a line containing two integers N and K. N is the number of Pokemons ($2 \le N \le 1000$), and K is the number of types ($2 \le K \le 100$).

The next N lines each contain three integers X, Y, and Z: the x-coordinate, the y-coordinate, and the type of a Pokemon. $-1,00,000,000 \le X \le 1,00,000,000$, $-1,00,000,000 \le Y \le 1,00,000,000$, and $1 \le Z \le K$.

For each test case, print a single line containing the minimum side of a square that contains Pokemons of K different types.