Полювання за скарбами!
Скрудж МакДак отримав карту стародавнього лабіринту Майядак, наповненого золотом та іншими скарбами. Він знає, що в лабіринті є рівно n кімнат, і хоче відвідати всі, щоб зібрати всі багатства. Кожна кімната має рівно один вихід до іншої кімнати. Жодна кімната не має більше одного входу з іншої кімнати. Основна проблема полягає в тому, що немає шляхів між лабіринтом і зовнішнім світом, а також між деякими парами кімнат. Скрудж вирішив скористатися послугами Підрозділу Телепортаційної Компанії Качок, щоб вирішити цю проблему. Він може телепортуватися в будь-яку кімнату всередині лабіринту або назовні. Але є ще одна проблема: кожен стрибок коштує величезну суму грошей, і МакДак повинен мінімізувати кількість телепортацій.
На карті Скруджа кімнати пронумеровані від 1 до N, і в кожній кімнаті вказано номер кімнати, куди можна перейти. На жаль, деякі номери пошкоджені через вік і тепер нерозбірливі.
Вам потрібно визначити очікувану суму грошей, яку Скрудж витратить на дослідження всіх кімнат і повернення з лабіринту, за умови, що його стратегія є оптимальною і всі можливі конфігурації лабіринту рівноймовірні. Він починає свою подорож ззовні лабіринту. Перший стрибок Скрудж робить безкоштовно.
Вхідні дані
На першому рядку введення задано ціле число T (0 < T ≤ 100) — загальна кількість тестових випадків. Кожен тестовий випадок описується двома рядками. На першому рядку є два цілі числа 1 < N ≤ 4000 — кількість кімнат і 0 ≤ c ≤ 1000 — вартість одного стрибка. На другому рядку є N чисел, 0 ≤ a_i ≤ N — номер кімнати, куди можна піти безпосередньо з i-ї кімнати. Якщо номер кімнати нерозбірливий, то a_i = 0. Усі тестові випадки розділені порожнім рядком. Сума N у всіх випадках не перевищує 4000. Гарантується, що всі вхідні дані є коректними, тобто існує принаймні один план, що відповідає вхідним даним.
Вихідні дані
Для кожного вхідного випадку ви повинні вивести одне число з плаваючою комою в окремому рядку — відповідь на задачу з абсолютною або відносною точністю 10^{-6}.