Отборочный раунд завершен

Задания

Показывать по одной задаче на странице / все задачи на одной странице

"A" Маленькие числа
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт

У мальчика Влада есть два любимых числа a и b. Недавно его в школе научили делить и умножать, и он сразу побежал делить и умножать свои любимые числа.

Сначала он написал в тетрадке числа a и b, после чего решил, что будет последовательно производить с ними одну из трёх операций:

  • Поделить оба числа на какой-то из их общих делителей;
  • Поделить a на один из его делителей g, а b умножить на g;
  • Поделить b на один из его делителей g, а a умножить на g.

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

Так как Влад ещё маленький, ему нравятся числа поменьше, потому он стремится минимизировать сумму чисел, написанных в тетрадке. Сам он не справляется. Помогите Владу определить, какую минимальную сумму чисел возможно получить такими операциями, и приведите пример пары чисел, которая может получиться в итоге.

Формат входных данных

Входные данные содержат несколько тестовых наборов. В первой строке задано количество тестов t (1 ≤ t ≤ 500).

Каждый тест описывается следующим образом: в единственной строке описания теста содержатся два числа a и b (1 ≤ a, b ≤ 109) — любимые числа Влада.

Формат выходных данных

Для каждого теста в отдельной строке выведите ответ на него — пару с минимальной суммой, которую можно получить применяя операции из условия.

Если ответов несколько, то разрешается вывести любой из них.

Примеры
Входные данные
2
4 5
4 6
Выходные данные
1 5
2 3
 

Отправить решение

Загрузить Максимальный размер - 256 Кб

Вход

ВКонтакте Facebook It.Mail

Забыли пароль?

Регистрация

На вашу электронную почту была
отправлена инструкция по восстановлению пароля.