MooBuzz

Interview

Time limit1sMemory limit512 MB

Summary

Given N up to 1e9, find the Nth positive integer that is not a multiple of 3 or 5, since those turns are replaced by Moo.

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

Problem

Farmer John's cows have recently become fans of a simple number game called "FizzBuzz". The rules are simple: standing in a circle, the cows count upward from one, each cow saying a single number when it is her turn. If a cow reaches a multiple of 3, she says "Fizz" instead of that number. If she reaches a multiple of 5, she says "Buzz" instead of that number. If she reaches a multiple of 15, she says "FizzBuzz" instead of that number. A transcript of the first part of a game is therefore:

1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16

Having a slightly more limited vocabulary, the cows' version of FizzBuzz says "Moo" instead of Fizz, Buzz, and FizzBuzz. The beginning of the cow version of the game is therefore:

1, 2, Moo, 4, Moo, Moo, 7, 8, Moo, Moo, 11, Moo, 13, 14, Moo, 16

Given $N$ ( $1 \leq N \leq 10^9$ ), determine the $N$ th number spoken in this game.

Input

The input consists of a single integer, $N$ .

Output

Print the $N$ th number spoken during the game.

Hint

The 4th number spoken is 7. The first 4 numbers spoken are 1, 2, 4, 7, since we skip over any time a cow says "Moo".

Examples1

Example 1
Input
```
4
```
Expected output
```
7
```