Maxim 有一个计算器。计算器有两个整数单元。最初,第一个单元格包含数字 1,第二个单元格包含数字 0。在一次移动中,您可以执行以下操作之一:
1. 假设当前第一个单元格包含数字 a,第二个单元格包含数字 b。写入第二个单元格编号b + 1;
2. 假设当前第一个单元格包含数字 a,第二个单元格包含数字 b。写入第一个单元格编号 a·b。
Maxim 想知道,有多少个整数 x (l ≤ x ≤ r),这样我们就可以将数字 x 写入计算器的第一个单元格,最多执行 p 次移动。
输入
第一行包含三个整数:l、r、p (2 ≤ l ≤ r ≤ 109, 1 ≤ p ≤ 100)。
行中的数字由单个空格分隔。
输出
在一行中打印一个整数——问题的答案。
示例
输入 #1
2 10 3
输出 #1
1
输入 #2
2 111 100
输出 #2
106
输入 #3
2 111 11
输出 #3
47