Number with the Most Divisors

Time limit1sMemory limit1024 MB

Summary

Given n up to 3,000,000, find the smallest number in 1..n with the most positive divisors, and report that divisor count.

Level: Medium4 of 10
Topics: Number theory, Math, Brute force, Implementation
Solved: No attempts yet

Problem

A number $n$ is given.

Write a program numdiv that finds a number between $1$ and $n$ inclusive that has the largest number of positive integer divisors.

Input

The first line of standard input contains a single integer $n$ .

Output

The first line of standard output must contain the number with the largest number of divisors.

The second line must contain the number of divisors of that number.

If several numbers between $1$ and $n$ have the largest number of divisors, output the smallest of them.

Constraints

$1 \le n \le 3\,000\,000$

Hint

Explanation of sample 2: The number $24$ has $8$ divisors: $1, 2, 3, 4, 6, 8, 12, 24$ . The number $30$ also has $8$ divisors: $1, 2, 3, 5, 6, 10, 15, 30$ . But $24$ is the smaller of the two.

Examples2

Example 1
Input
```
20
```
Expected output
```
12
6
```
Example 2
Input
```
30
```
Expected output
```
24
8
```