Перемішати
Мій офіс розташований досить далеко від дому, і щодня я їжджу туди автобусом. Це займає багато часу, а через затори тривалість поїздки не є постійною. Щоб максимально використати цей час, я завжди беру з собою музичний плеєр.
Мій музичний плеєр має режим «перемішування». У цьому режимі плеєр випадково вибирає трек, який ще не був відтворений у цій сесії, і починає його відтворення. Він продовжує це робити, поки я не зупиню відтворення або не будуть відтворені всі треки в цій сесії. Для цілей цієї задачі можна припустити, що всі треки мають однакову тривалість. Щоб вибрати випадковий трек, плеєр веде список вже відтворених треків. Тобто, якщо я зараз слухаю один трек, з наступної сесії перемішування цей трек буде позначено як відтворений. Щоб вибрати випадковий трек, плеєр завжди використовує таку стратегію, що вибір старого треку (вже прослуханого) вдвічі ймовірніший, ніж нового треку (не прослуханого).
Я їду до офісу вранці та повертаюся додому ввечері. Це займає щонайменше p хвилин і щонайбільше q хвилин, щоб дістатися до офісу. Час, необхідний для цього, завжди буде цілим числом. Можна припустити, що всі часи подорожі є рівноймовірними (тобто, якщо p = 2 і q = 4, і якщо P(t) є ймовірністю доїхати до офісу за t хвилин, то P(2) = P(3) = P(4)). Якщо всі треки мають тривалість 1 хвилину, скільки днів у середньому потрібно, щоб прослухати всі пісні?
Вхідні дані
Перша строка введення містить ціле число T(≤ 10053), кількість тестових випадків.
Кожен тестовий випадок містить 5 цілих чисел, N (1 ≤ N ≤ 75), p_1, q_1, p_2, q_2 (0 ≤ p_1, q_1, p_2, q_2 ≤ 30, p_1 ≤ q_1, p_2 ≤ q_2), де N — кількість пісень, p_1, q_1 — мінімальна та максимальна кількість пісень, прослуханих протягом дня, а p_2, q_2 — мінімальна та максимальна кількість пісень протягом ночі.
Вихідні дані
Для кожного тестового випадку виведіть номер тестового випадку, а потім очікувану кількість днів, необхідних для прослуховування всіх пісень. Якщо неможливо прослухати всі пісні, виведіть "IMPOSSIBLE". Помилки менше 10^{-6} будуть допускатися.
Опис зразка випадку 1:
Кожного дня я буду слухати або 1 пісню, або жодної. Ймовірність прослухати 1 пісню становить
Ймовірність не прослухати жодної пісні становить
Отже, ймовірність прослухати пісню в перший день =
Ймовірність прослухати пісню на другий день =
Ймовірність прослухати пісню на другий день =
І так далі. Отже, очікувана кількість днів буде:
Нескінченна сума оцінюється як , і таким чином, очікувані дні =