Музей Bizarre Argentinean Pocket Calculators (BAPC) нашел замечательного живописца, чтобы сделать красивую картину пола в музее. Все стены в музее прямые, и любые две соседние стены пересекаются под прямым углом. Все несмежные стены попарно не пересекаются. Кроме того, в комнате, в которой должна появиться картина, нет столбов. Следовательно, это прямолинейный простой многоугольник.

Дизайн для картины квадратный. Музей хочет, чтобы картина была как можно больше. Кроме того, его следует поместить так, чтобы края квадрата были параллельны стенам. Найдите максимально возможную ширину для рисунка.

Входные данные

Первая строка содержит количество тестов, не более 100. Далее для каждого теста:

• первая строка содержит число n (4 ≤ n ≤ 1 000) - число углов в комнате.
• n строк, каждая из которых содержит два целых числа x и y (0 ≤ x, y ≤ 100 000): координаты каждого угла комнаты.

Углы заданы по часовой стрелке.

Выходные данные

Для каждого теста вывести в отдельной строке максимальную ширину квадратной картины, которая помещается на полу музея.