Недавно Ёжик вспомнил одно из своих любимых занятий детства — собирание пазлов, и увлёкся им с новой силой. Целыми днями сидел он со своим другом и копался в тысячах маленьких кусочков картинки, отыскивая один за другим нужные элементы.

Вскоре Ёжику пришла в голову замечательная идея: вместо того чтобы покупать готовые пазлы, можно самому брать большой лист с какой-нибудь картиной и разрезать его на множество маленьких прямоугольных кусочков, затем перемешивать их и решать получившуюся головоломку, пытаясь собрать картину обратно. Так получается даже более сложная задача, чем классический пазл: ведь теперь все фрагменты имеют одинаковую прямоугольную форму, и собирать картину можно, только полагаясь на рисунок.

Все кусочки головоломки получаются одинакового размера X × Y, потому что картина разрезается сначала горизонтальными разрезами с шагом X, а затем — вертикальными разрезами с шагом Y. Если мы обозначим первоначальные размеры картины через A × B, то A должно делиться на X, B должно делиться на Y (X и Y — целые числа).

Однако не любое такое разрезание картины даст хороший пазл. Ёжик считает пазл хорошим, если никакие два кусочка в нём не совпадают (при сравнении кусочки разрешается поворачивать, но не переворачивать).

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