给定三个整数 $n, m, k$，求满足以下条件的数对 $(a, b)$ 的数量：

• $|a|, |b| \le m$
• $a, b \in \mathbb{Z}$，即 $a$ 和 $b$ 为整数
• $|S| = k$，其中 $S$ 是方程 $x^n + a \cdot x + b = 0$ 的有理数根集合，$|S|$ 为集合 $S$ 的大小。特别地，恰好存在 $k$ 个不同的有理数 $x$ 满足该方程。

注：当且仅当存在两个整数 $p$ 和 $q$ ($q \neq 0$) 使得 $x = \frac{p}{q}$ 时，$x$ 是一个有理数。

输入包含多组测试数据，以文件结束符（EOF）终止。对于每组测试数据： 第一行包含三个整数 $n, m, k$。

• $1 \le n, m, k \le 5 \times 10^5$
• 对于每组输入，所有测试数据的 $m$ 之和不超过 $5 \times 10^5$。

对于每组测试数据，输出一个整数，表示满足条件的数对数量。

样例

样例输入 1

2 1 1
2 2 2
3 3 3

样例输出 1

1
7
1

说明

对于第一组测试数据，只有方程 $x^2 = 0$ 有一个有理数根。

对于第二组测试数据，以下 7 个方程中的每一个都有两个不同的有理数根：

• $x^2 - 2x = 0$
• $x^2 - x = 0$
• $x^2 - x - 2 = 0$
• $x^2 - 1 = 0$
• $x^2 + x = 0$
• $x^2 + 2x = 0$
• $x^2 + x - 2 = 0$