Деяким інженерам набридло мати справу з різними способами кодування повідомлень, тому вони вирішили придумати свої власні. У новій схемі закодоване повідомлення складається з послідовності цілих чисел, що представляють символи повідомлення, розділених пропусками. Кожне ціле число знаходиться в межах від \textbf{1} до \textbf{M }включно. На жаль, було вирішено стиснути закодоване повідомлення, видаливши усі пропуски! Вам слід з'ясувати, скільки різних вихідних повідомлень можуть відповідати заданому закодованому стиснутому повідомленню. Оскільки це число може бути велике, відповідь слід виводити за модулем \textbf{4207849484} (\textbf{0xfaceb00c} в шістнадцятковій системі числення). Наприклад, закодоване повідомлення "\textbf{12}" могло бути спочатку "\textbf{1 2}" або "\textbf{12}". Довжина закодованого стиснутого повідомлення може змінюватися від \textbf{1} до \textbf{1000} символів включно. \InputFile Перший рядок містить кількість закодованих повідомлень \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{25}), які потрібно проаналізуват. Далі йде \textbf{N} повідомлень, кожне з яких задано цілим числом \textbf{M} (\textbf{2} ≤ \textbf{M} ≤ \textbf{255}) - найбільшим кодом символу у базі кодування, та саме стиснене повідомлення. Відомо, що \textbf{1} ≤ довжина стисненого закодованого повідомлення ≤ \textbf{1000}. \OutputFile Для кожного тесту, пронумерованого числами від \textbf{1} до \textbf{N}, вивести рядок "\textbf{Case #i:} ", після чкого йде кількість різних повідомлень, які задають у стисненому вигляді вхідну послідовність. Якщо таких повідомлень не існує, то вивести \textbf{0}.