Модуль: B27 (C4) - анализ пар


Задача

1 /23


НОД для пары чисел

Задача

Имеется набор данных, состоящий из пар положительных целых чисел. Для каждой пары чисел находится значение А – наибольший общий делитель. 

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

Программа считается эффективной по времени, если время работы программы пропорционально количеству пар чисел N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. 

Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 100 килобайт.


Входные данные
На вход программе в первой строке подаётся количество пар N (\(1 <= N <= 100000\)). Каждая из следующих N строк содержит два натуральных числа, не превышающих 1000. 

 

Входные данные
Выведите ответ на задачу

 

 

Примеры
Входные данные Выходные данные
1
6
1 3 
5 15  
6 9  
5 4  
3 3  
36 40  
3 1