Поликарпу нравится делать подарки Прасковье. Вот и сейчас он купил две плитки шоколада, каждая из них имеет форму прямоугольника из долек. Первая плитка имеет размеры a₁ × b₁ долек, а вторая — a₂ × b₂ долек.

Поликарп хочет угостить на большой перемене Прасковью одной плиткой, а вторую съесть сам. Кроме того, он хочет подчеркнуть одинаковую значимость ума Поликарпа и красоты Прасковьи, поэтому плитки должны содержать одинаковое количество долек.

Чтобы сделать плитки равными по количеству долек, Поликарп каждую минуту съедает немного шоколада. Каждую минуту он:

• либо разламывает одну плитку ровно пополам (вертикально или горизонтально) и съедает ровно половину шоколадки,
• либо отламывает от плитки ровно одну треть (вертикально или горизонтально) и съедает ровно треть шоколадки.

В первом случае от плитки останется половина, а во втором — две трети.

Не всегда возможны оба развития событий, а иногда бывает, что Поликарп вообще не может отломить половину или треть. Например, если плитка имеет размер 16 × 23, то от нее можно отломить половину, но нельзя одну треть. Если плитка имеет размер 20 × 18, то от нее можно отломить как половину, так и треть. Если плитка имеет размер 5 × 7, то отломить как половину так и треть невозможно.

Какое минимальное количество минут понадобится Поликарпу, чтобы сделать обе плитки одинаковыми по количеству долек в них? Найдите не только искомое минимальное количество минут, но и возможные размеры плиток после их вынужденного «уравнивания».