在数学课上,老师要求每个学生想出自己的幸运数字。作为数论爱好者,彼得选择了素数。鲍勃更有创意。他说数字t就是他的幸运数字,如果可以表示为:
t = a2 + b2,
现在,男孩们决定找出间隔 [l, r] (l ≤ r) 中的多少天适合结对编程。他们认为,当且仅当数字 i 同时对 Peter 来说是幸运的并且对 Bob 来说是幸运的时,i (l ≤ i ≤ r) 适合结对编程。帮助孩子们找出这样的天数。
输入
输入的第一行包含整数 l, r (1 ≤ l, r ≤ 3·108)。
输出
在唯一的一行中打印段 [l, r] 上的天数,这同时对 Peter 和 Bob 来说是幸运的。
示例
输入 #1
3 5
输出 #1
1
输入 #2
6 66
输出 #2
7