Міністерство національної оборони (МНО) хоче з’єднати кілька північних форпостів бездротовою мережею. Для створення мережі використовуватимуться дві різні технології зв’язку: кожна застава матиме радіоприймач, а деякі застави додатково матимуть супутниковий канал.
Будь-які два аванпости з супутниковим каналом можуть підтримувати зв’язок через супутник, незалежно від їх розташування. В іншому випадку два аванпости можуть підтримувати зв’язок по радіо, лише якщо відстань між ними не перевищує d, що залежить від потужності приймачів. Вища потужність дає більше d, але коштує дорожче. З міркувань купівлі та обслуговування приймачі на аванпостах мають бути ідентичними, тобто значення d однакове для кожної пари аванпостів.
Ваше завдання — визначити мінімальне d, необхідне для приймачів. Між кожною парою аванпостів має бути принаймні один шлях зв’язку (прямий чи опосередкований).
Перший рядок містить число n — кількість тестів. Перший рядок кожного тесту містить кількість супутникових каналів s (1≤s≤100) і кількість аванпостів p (s<p≤500). Далі йдуть p рядків, в яких вказуються координати (x,y) кожного форпосту в км (координати є цілими числами від 0 до 10000).
Для кожного випадку виведіть мінімальне d, необхідне для приєднання до мережі. Вихідні дані мають бути вказані з точністю до 2 десяткових знаків.