Гра Ані
Маленька дівчинка на ім'я Анна Спетрінг любить грати в таку гру. Вона малює коло на папері. Потім додає ще одне коло і з'єднує його з першим колом лінією. Далі вона малює ще одне коло і з'єднує його лінією з одним із вже намальованих кіл. Вона продовжує в тому ж дусі, поки не намалює n кіл, причому кожне нове коло з'єднується з одним із попередніх. Її кола ніколи не перетинаються, і лінії також не перетинаються. Нарешті, вона нумерує кола від 1 до n у довільному порядку.
Скільки різних малюнків вона може створити, якщо вони містять рівно n кіл? Два малюнки вважаються різними, якщо на одному з них є лінія, що з'єднує коло з номером i з колом з номером j, а на іншому такої лінії немає.
Вхідні дані
Перший рядок містить кількість тестів t. Кожен тест представлений рядком, що містить число n (0 < n ≤ 100).
Вихідні дані
Для кожного тесту виведіть рядок у форматі "Case #x:", за яким слідує res, де res - остача від ділення відповіді на 2000000011.