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
Siddharth Singh: 2016-07-20 11:42:07

Came Back And Conquered After 8 months :D <3

vaibhav138: 2016-07-20 04:11:59

Tricky one :)
Think like a beginner .

Piyush Kumar: 2016-06-09 13:36:48

The concept is fairly simple. I wonder why there are only a handful submissions!

KD : 2016-06-06 17:48:07

use long long int ........otherwise it will give WA ...AC in 2nd go -_-

Sarthak Munshi: 2016-06-04 10:57:53

@Ruhan can you have a look at my submissions ? Its been 12 WA now .

Last edit: 2016-06-15 19:50:36
Ruhan Habib: 2016-05-31 08:42:32

@sunny59 yes. and consider only i > 0

rainy jain : 2016-05-20 08:31:10

@Ruhan is your approach different from mine. Id:16948914

Last edit: 2016-05-31 14:16:12
Shashank Tiwari: 2016-04-15 05:42:56

1. Please make sure that for some cases there is no such 'i' and in such a case print 0.
ex: a=4 , b=2. Here output should be 0.

2. Every thing fits in int. So need of long long.

Last edit: 2016-04-15 05:44:24
sri: 2016-03-05 14:47:14

what is the range of i?

mcjoshi: 2016-02-27 06:12:13

OMG! AC in 3rd attempt
Moved from TODO list to SOLVED in 10 days.
btw just 18 lines of code in C


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