Unchanging numbers

Time limit2sMemory limit512 MB

Summary

For a given digit count n, decide whether the n-digit idempotent number ending in 5 or the one ending in 6 is larger.

Level: Medium5 of 10
Topics: Number theory, Math, Implementation
Solved: No attempts yet

Problem

For a natural number $n$ , consider the $10^n$ numbers written with $n$ digits, from 00...0 ( $n$ zeros) to 99...9 ( $n$ nines). Call such a number an unchanging number if the last $n$ digits of its square are the same as the number itself.

Whatever the digit count $n$ is, there are always exactly four unchanging numbers. Two of them are 00...0 and 00...01, and of the other two, one has 5 as its last digit and the other has 6. For $n = 4$ the unchanging numbers are 0000, 0001, 0625 and 9376. Here $0000^2 = 0$ , $0001^2 = 1$ , $0625^2 = 390625$ and $9376^2 = 87909376$ , and every square ends with the original four digits.

Given the digit count $n$ , write a program that prints which of the two is larger, the unchanging number whose last digit is 5 or the unchanging number whose last digit is 6.

Input

The first line contains the digit count $n$ . ( $1 \le n \le 10000$ )

Output

Print 5 on the first line if the unchanging number whose last digit is 5 is larger, or 6 if the unchanging number whose last digit is 6 is larger.

Examples2

Example 1
Input
```
4
```
Expected output
```
6
```
Example 2
Input
```
3
```
Expected output
```
5
```