C - すぬけそだて――ごはん――

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 400

問題文

目当ての「マタタビ」を手に入れたあなたは、「すぬけそだて」を本格的に遊び始めました。

都市の道端とはいえやはり自然は弱肉強食の世界で、拾われたばかりのすぬけ君は弱りきっていました。 あなたは、ゲーム内アイテムを食べさせてあげることで、すぬけ君の体力を回復させようとしています。

さて、すぬけ君は好物が整数の書かれたカードであるという変わったねこです。カードをすぬけ君に与えると、あなたはむしゃむしゃと幸せそうにカードを食べるすぬけ君の愛らしい姿を眺めることができます。 しかし、カードを与えているうちに、あなたはカードを食べてもすぬけ君が喜ばないことがあることに気付きました。また、以下の性質を発見しました。

  • すぬけ君は、その日にこれまでに食べたどのカードに書かれた整数とも互いに素である整数の書かれたカードを食べたとき、喜ぶ。そうでないとき、悲しむ。

今日のカードショップには A 以上 B 以下の整数の書かれたカードが 1 枚ずつ売られています。 あなたは、このうちの 0 枚以上の任意の枚数を購入し、すべてのカードをすぬけ君に与えることにしました。このとき、すぬけ君を 1 度でも悲しませてはいけません。

カードの買い方は何通りあるでしょうか。

制約

  • 1 \leq A \leq B \leq 10^{18}
  • B-A\leq 35

入力

入力は以下の形式で標準入力から与えられる。

A B

出力

カードの買い方の個数を出力せよ。


入力例 1

2 4

出力例 1

6

2 の書かれたカードと 4 の書かれたカードを同時に含まないものすべてが条件を満たします。これは 6 通りあります。


入力例 2

5 9

出力例 2

20

入力例 3

123456789987654321 123456789987654356

出力例 3

105728