Luka found a very unusual game board in his attic. Surprisingly, it consists of
What makes the board unusual is the way in which the cells are coloured. Each cell is either grey or white:
- white, if the row and column numbers of the cell, when represented in binary, have at least one digit 1 in the same position. For example, the cell
would be white. - grey, otherwise. For example, the cell
would be grey.
The following image shows a board of size
Luka's hedgehog likes walking on this unusual board and does it in an unusual way. The hedgehog starts his walk in the cell
After visiting
Knowing the dimensions of the board and the number
Input Specification
The first line contains two integers
The second line contains the integer
Note that this number may not fit in a
Output Specification
Output the number of grey cells the hedgehog visits.
Grading
In test cases worth
Sample Input 1
10 10
6
Sample Output 1
5
Sample Input 2
3 5
11
Sample Output 2
8
Sample Input 3
10 10
100
Sample Output 3
51
Comments