Маленькая девочка по имени Анна Спетринг любит играть в следующую игру. Она рисует круг на бумаге. Затем она рисует еще один и соединяет его с первым кругом линией. Затем она рисует еще один и соединяет его линией с одним из первых двух кругов. Она продолжает таким образом, пока не нарисует n кругов, и каждый из них соединится с одним из ранее нарисованных кругов. Ее круги никогда не пересекаются, и линии тоже никогда не пересекаются. Наконец, она нумерует круги от 1 до n в произвольном порядке.

Сколько разных картинок она может нарисовать, содержащих ровно n кругов? Два изображения различны, если на одном из них есть линия, соединяющая круг с номером i с кругом с номером j, а на другом нет.

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

Первая строка содержит количество тестов t. Каждый тест представляет собой строку, содержащую число n (0 < n ≤ 100).

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

Для каждого теста выведите строку, содержащую "Case #x:" за которой следует res, где res - остаток от деления ответа на 2000000011.