Neo has to enter again in the Matrix. The Matrix is represented as a two dimensional plane of coordinates x-y. When the Matrix was born, agent Smith showed up and imposed control. Unfortunately he is not alone, other agents are around him to do the same work. An agent is at some point in the Matrix given by a pair ( Xi, Yi ). Neo is now very furious because he cut his hair and wants to attack two agents. Neo can travel any distance to attack the first agent, but later he will be very tired, so he wants to walk the smallest distance possible to the next agent.

Neo is very busy conquering Trinity, who is a very difficult girl in terms of taking her out on a date, and he has no time to think about silly things like this, all he can think about is fun and war... Please, help him find the smallest distance possible from the first agent to the second.

Input

In the first line of the input appears one integer: T. This representes that your program must solve exactly T data sets for Neo. Each data set is not related to the previous one.

In the first line of each data set appears one integer: N, representing that there are N agents in that layout of agents. Following this line, N pairs of integers will appear, each pair in a new line, representing the position of each agent.

Output

For each data set your program must output only one line represents the smallest distance between two agents. Please for avoid decimal roundings write the result whit zero decimal places after the comma.

Example

Input: