FCDC - Factorial Modulo


You are given 2 integers a, b. Find the number of i for which i! is divisble by a but not b. if i! is divisible by a and b, then you should not count that i.

Input

One line that contains a and b.

Output

Output the result in one line.

Example

Input:
2 3

Output:
1

Constraints

 1 ≤ a ≤ b ≤ 107

Explanation

2! is the only factorial which is divisible by 2 and not divisible by 3.


hide comments
visleck: 2017-08-01 22:43:58

@ruhan habib can u please check where my solution is going wrong. I have checked my solution for all cases given in spojtoolkit and it gives the same ans (submission id-19900630)

Last edit: 2017-08-01 22:46:49
amulyagaur: 2017-07-25 19:00:19

No need to brag about AC in one go ... and 0.00 sec... the test cases are weak..
5 63.. the ans should be 2 ... while many submission give 1 as the answer

an6285: 2017-07-17 17:28:56

Amazing Problem.AC in 2nd go, a must try problem ;)

sagnik_66: 2017-05-29 16:34:18

Done finally :D

Last edit: 2017-05-29 16:38:57
sarelfeniel: 2017-02-24 18:47:30

Very nice problem!

Nemanja Stojanovic: 2016-11-09 02:11:51

Can you check my submission 18137234 ?

I think it should work, but gives wrong answer. thanks

citransvostok: 2016-11-05 14:24:13

vzyal 280 strok, kak sdelat eto meneye chem xa 50?

Last edit: 2016-11-05 14:26:47
ashishranjan28: 2016-11-01 07:29:11

a must try question

Amitayush Thakur: 2016-10-02 08:33:31

Weak test cases. Please include 5 63 in the test case, because a solution which gives answer as 1 for 5 63 also passes. While the answer should be 2.

poda_venna: 2016-09-02 17:16:34

the feeling of cracking thisssssss


Added by:Ruhan Habib
Date:2015-11-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Own Problem