Password

Interview

Time limit2sMemory limit2048 MB

Summary

Given the password length n, find the minimum and maximum number of non-letter characters a valid password of that length can contain.

Level: Medium4 of 10
Topics: Greedy, Implementation, Math
Solved: No attempts yet

Problem

After another leak of personal data, the administrator of Pochta.com decided to tighten the password rules for employees. Each employee's password must be exactly $n$ characters long, and at least one non-letter character must appear among every three consecutive characters. The non-letter characters must also be placed at the center of the password: one center character if $n$ is odd, or the two characters closest to the center if $n$ is even.

For $n = 9$ , the passwords p4ss\#or0s and 1a2b34CD5 are valid. The password 1234a56bc is invalid because its fifth character must be a non-letter. The password 9ASE\#orkd is invalid because it has three letters in a row.

For $n = 6$ , the passwords ab23bc and 5a428E are valid, while 111e11 and 4sy1um are invalid.

The employees want to know the minimum and maximum number of non-letter characters that a password of a given length can contain. Find both.

Input

The first line contains an integer $n$ , the length of the password ( $1 \le n \le 1\,000\,000$ ).

Output

Print two integers separated by a space: the minimum and the maximum number of non-letter characters in the password.

Examples3

Example 1
Input
```
1
```
Expected output
```
1 1
```
Example 2
Input
```
2
```
Expected output
```
2 2
```
Example 3
Input
```
3
```
Expected output
```
1 3
```