Counting Gray Cells on a Rectangular Grid

We are given a rectangular grid of size (r \times c), which is subdivided into (r\times c) unit cells. The rows are numbered from (0) to (r-1) from top to bottom, and the columns are numbered from (0) to (c-1) from left to right.

Each cell located at row (x) and column (y) is colored as follows: if [ x \oplus y = x + y, ] then the cell is gray; otherwise, it is white. (Note that (x \oplus y = x+y) if and only if (x) and (y) have no common set bit, i.e. (x & y = 0).)

A person walks along the grid in row-major order, starting from cell ((0, 0)), then ((0, 1)), and so on, moving left to right in a row and then proceeding to the next row. The person visits exactly (k) cells (if (k > r\times c), only the (r\times c) available cells are considered). Write a program that counts how many gray cells are visited during these (k) steps.

inputFormat

The input consists of a single line containing three space-separated integers: (r), (c) and (k), representing the number of rows, the number of columns, and the number of visited cells, respectively.

outputFormat

Output a single integer representing the number of gray cells visited in the first (k) cells traversed in row-major order.

sample

10 10 5

5