There is a data set consisting of pairs of positive integers. For each pair of numbers, the value A – greatest common divisor.
Write a time- and memory-efficient program that will determine which A value is most common. If multiple A values occur the same maximum number of times, output them in descending order.
A program is considered time efficient if the program execution time is proportional to the number of N pairs, i.e. when N increases by k times the running time of the program should increase no more than k times.
A program is considered memory efficient if the amount of memory used in the program to store data does not depend on the number N and does not exceed 100 kilobytes.
Input
The input to the program in the first line is the number of N pairs (\(1 <= N <= 100000\)). Each of the following N lines contains two natural numbers not exceeding 1000.
Input
Output the answer to the problem
Examples
| # |
Input |
Output |
| 1 |
6
1 3
5 15
6 9
5 4
3 3
36 40
|
3 1 |