Рассмотрим устройство, выполняющее некоторую работу. Помимо этого оно должно контролировать свою температуру. Температура не должна быть слишком высокой или слишком низкой. Однако в устройстве испортился механизм контроля температуры, и теперь устройство работает следующим образом. Каждую минуту выбирается и выполняется один из возможных способов изменения температуры. Каждый способ выбирается с некоторой заданной вероятностью в зависимости от текущей температуры.

Вам даны вероятности изменений температуры. Вычислите вероятность того, что температура будет находиться в заданном интервале в течение определённого времени.

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

Первая строка ввода содержит количество тестов T (1 ≤ T ≤ 20). Первая строка каждого теста содержит четыре целых числа A, B, C, N, где A – минимальная разрешённая температура, B – максимальная разрешённая температура, C – начальная температура, N – время работы прибора в минутах. 0 ≤ A ≤ B ≤ 30, A ≤ C ≤ B, 0 ≤ N ≤ 30.

Каждая из следующих B – A + 1 строк содержит 7 неотрицательных целых чисел, в сумме дающих 100 – вероятность в процентах изменения температуры на –4, –3, –2, –1, 0, 1 и 2 градуса соответственно. K-я строка (1 ≤ K ≤ B – A + 1) описывает вероятности для ситуации, когда текущая температура равна A + K – 1.

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

Выведите T строк вида Case #A: B, где A – номер теста (начиная с 1), B – искомая вероятность для данного теста. Ответ надо вывести без округления. Гарантируется, что ответ имеет не более 60 десятичных знаков после запятой.