P5834 [USACO19DEC] MooBuzz S

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.

The input contains one integer $N$.

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

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