Герой этой задачи придумывает новый термин в информатике: Бесконечный граф. Он хочет, чтобы число ребер и вершин в таком графе было бесконечным.

Несложно догадаться, что такой граф не получится задать списком вершин и ребёр. Поэтому герой решил задать его с помощью двух правил:

• Все вершины графа пронумерованы целыми числами от $1$ до $\infin$;

• Между вершиной $u$ и $v$ есть неориентированное ребро, если $u$ целочисленно делится на $v$. Вес такого ребра будет равен $u / v$.

Научитесь искать кратчаший путь между двумя вершинами $a$ и $b$ в таком графе (длина пути – сумма весов ребер на нём).

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

В первой строке записано число $q$ – количество запросов ($1 \le q \le 6000$).

Каждая из следующих $q$ строк содержит числа $a$ и $b$ – вершины бесконечного графа, между которыми нужно найти кратчайший путь ($1 \le a, b \le 10^9$).

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

Для каждого запроса с новой строки выведите одно число – кратчаший путь между вершинами $a$ и $b$.

Подзадачи