На координатній площині розташовані \(N\) міст. Місто \(i\) розташоване в координатах (\(x_i, y_i\)). Відстань між містом \(i\) та містом \(j\) дорівнює ~\sqrt{(x_i-x_j)^2 + (y_i-y_j)^2}.

Є \(N!\) можливі шляхи, щоб відвідати всі ці міста один раз. Нехай довжина шляху — це відстань, яку ми подолали, коли ми починаємо з першого міста, відвідуємо друге, третє,... міста, і прибуваємо до останнього міста (припустимо, що ми рухаємося по прямій від одного міста в інше).

Обчисліть середню довжину цих \(N!\) шляхів.

Формат вхідних даних

Перший рядок містить ціле число \(N\) (\(2 \le N \le 8\)).

Наступні  \(N\) рядків містять цілі числа \(x_i, y_i\) (\(-1000 \le x_i,y_i \le 1000\))

Формат вихідних даних

У вихідний потік виведіть середню довжину шляхів.

Ваш результат буде вважатися правильним, якщо абсолютна різниця від результату становить не більше \(10^{-6}\).

Приклад вхідних даних

3
0 0
1 0
0 1

Приклад вихідних даних

2.2761423749

Приклад вхідних даних

2
-879 981
-866 890

Приклад вихідних даних

91.9238815543

Приклад вхідних даних

8
-406 10
512 859
494 362
-955 -475
128 553
-986 -885
763 77
449 310

Приклад вихідних даних

7641.9817824387