Description

Farmer John’s cows have recently become enthusiastic players of a simple number game called “FizzBuzz.” The rules of this game are simple: the cows stand in a circle and count in order starting from $1$, and each cow says one item when it is her turn. If the number a cow is about to say is a multiple of $3$, she should say Fizz instead of the number. If it is a multiple of $5$, she should say Buzz instead of the number. If it is a multiple of $15$, she should say FizzBuzz instead of the number. Therefore, the beginning of the record of the game is:

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

Due to a limited vocabulary, in the cows’ version of FizzBuzz they use Moo to replace Fizz, Buzz, and FizzBuzz. Therefore, the beginning of the record of the cows’ game is:

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

Given $N$, find the $N$-th number that is spoken in this game.

Input Format

The input contains one integer $N$.

Output Format

Output the $N$-th number spoken in the game.

4

7

Hint

About partial scoring:

Test point $1$ is the sample.

Test points $2 \sim 5$ satisfy $N \le 10^6$.

For $100\%$ of the testdata, $1 \leq N \leq 10^9$.

Problem by: Brian Dean.

Translated by ChatGPT 5