Luka 有一个与众不同的棋盘，棋盘是一个R行C列的矩形，行从上到下编号从0到R-1，列从左到右编号从0到C-1.棋盘被染成黑白两种颜色。染色规则如下：
如果一个格子的行数和列数的二进制位至少有一个1相同则被染成白色。如方格（4，5）（4的二制数为100，5的二进制数为101，它们的最高位的1相同）其它的为黑色。如（2，5）；如下图为10-10的棋盘。

Luka在棋盘上按上图画的路线移动。从（0，0）开始，现在的问题是当他走了K步后，总共走过了多少个黑格子。

输入：第一行两个数分别表示R（$\le 1000000$）和C($\le 1000000$)；第二行一个数K表示走过的步数。($1 \le k \le R \times C $ )注意K会超过32位整数。

输出：
一个正整数，表示经过的黑格子个数。
样例：
输入
10 10
6
输出：
5
输入：
3 5
11
输出：
8
输入：
10 10
100
输出：
51
注意：对于50%的数据$K \le 1000000$.