Скрыть
В игре "Цена верна", в разделе "Закрыть", игроки пытаются выиграть новый автомобиль, угадывая его фактическую розничную цену, используя доску с возможными числами, как показано ниже:
Игрок выбирает по одному числу из каждого столбца, чтобы составить свою ставку. Например, используя приведённую доску, первое число в цене автомобиля может быть 1 или 3; второе — 9, 4 или 2; третье — 0, 6, 8 или 4; и так далее. Числа не могут перемещаться между столбцами.
После того как игрок делает свою ставку, Дрю Кэри зажигает правильные числа в ставке. Если у игрока нет правильных чисел, игра заканчивается, и он проигрывает; если есть хотя бы одно правильное число, игра продолжается.
Если игра продолжается, игроку предоставляется возможность выбрать новые числа из тех столбцов, где были ошибки. Он будет закрывать неправильные числа другими вариантами из тех же столбцов. Дрю Кэри снова зажигает любые новые правильные цифры. Если у игрока нет новых правильных чисел, игра заканчивается, и он проигрывает; если есть хотя бы одно новое правильное число, игра продолжается.
Например:
Игрок выбирает начальную ставку 14677}. \textbf{1}, \textbf{4} и первая \textbf{7} верны (\textbf{c} обозначает правильное, \textbf{x} — неправильное, а \textbf{v} обозначает столбец, требующий последующего выбора в примере). Игрок заменяет неправильные \textbf{6} и \textbf{7} на \textbf{8} и \textbf{3} для второй ставки \textbf{14873. 3 верна, но 8 неверна. На этом этапе у игрока 50/50 шанс. Он выберет 4 или 0 и либо выиграет автомобиль, либо проиграет игру.
Спонсоры шоу хотят знать, как часто их автомобили раздаются. Предполагается, что игроки выбирают числа равномерно из оставшихся.
Входные данные
Спонсор будет исследовать множество вариантов, с ценами до 7 цифр. Поэтому файл ввода начинается с строки, содержащей целое число N ≤ 5000, количество тестов для исследования. Далее следуют тесты.
Каждый тест начинается с целого числа d, 0 < d ≤ 7, количества цифр в цене автомобиля. Затем следуют d строк с непустыми строками *различных* цифр в диапазоне от 0 до 9. Каждая из этих строк представляет собой *столбец* цифр в игре. Первая строка — это самый левый столбец; последняя — самый правый. 0 возможен как первая цифра в цене автомобиля.
Выходные данные
Ваша программа должна вывести вероятность выигрыша автомобиля игроком, округленную до 3 знаков после запятой.