M. Memory Management
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output
The floppy disk used for the BAPC. CC0 1.0 by Peter Astbury on Wikimedia Commons

You are working on your new problem for the Benelux Algorithm Programming Contest (BAPC): FizzBuzz. Given two natural numbers $$$a$$$ and $$$b$$$, the contestant's program should print the natural numbers in ascending order, starting at (1), with three exceptions:

  • If $$$k$$$ is a multiple of $$$a$$$, the program should print "Fizz".
  • If $$$k$$$ is a multiple of $$$b$$$, it should print "Buzz".
  • If both hold, it should print "FizzBuzz".

Unfortunately, this year, the budget for the BAPC is rather minimal. Therefore, the output of the contestants is stored on floppy disks which can only hold (1440) KiB (({1 474 560}) bytes). It is your job to make sure that the correct output of a solution fits on such a floppy disk.

Given such $$$a$$$, $$$b$$$, and a natural number $$$n$$$, up to which integer (k) does the FizzBuzz sequence of (k) integers fit in (n) characters? Whitespace such as newlines or spaces should not be counted as characters.

An example of a FizzBuzz sequence of $$$11$$$ integers for $$$a=2$$$ and $$$b=3$$$ is given by this string of length $$$37$$$: "1FizzBuzzFizz5FizzBuzz7FizzBuzzFizz11".

Input

The input consists of:

  • One line with two integers $$$a$$$ and $$$b$$$ ($$$2\leq a,b \leq {1\,474\,560}$$$).
  • One line with an integer $$$n$$$ ($$$1\leq n\leq {1\,474\,560}$$$), the number of bytes of storage available.
Output

Output the largest integer (k), such that the FizzBuzz sequence from (1) up to and including (k) requires at most (n) bytes of storage.

Examples
Input
2 3
10
Output
3
Input
2 4
15
Output
5