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
[Lakshman]: 2015-11-12 11:26:50

My complete brute force code got AC in 0.0 s with python. test case are really week.

vijay77794: 2015-11-12 05:21:17

easy if u get the logic.......ac in 2nd go...:)

Vipul Srivastava: 2015-11-10 08:24:16

@Prakhar: There are no constraints on i according to the question. It can be anything. Analyse the problem for further insight.

Last edit: 2015-11-10 08:48:07
Prakhar Dev Gupta: 2015-11-10 05:41:18

@[LAxman] It can be any I guess.
The thing I wanted to ask was.. there is nothing clearly specified for "i".
Does i lie between a and b or could it be any from 1 to b?

[Lakshman]: 2015-11-10 05:29:16

a and b both are prime numbers or it can be any number?

Ruhan Habib: 2015-11-09 12:43:06

I've changed the test case, and rejudging has started

wisfaq: 2015-11-09 11:57:18

Ruhan, did you change the testcases?
If so you should rejudge and make a post that you did so

(Ruhan) => Yes, I changed the testcase, and rejudging is in process.

Last edit: 2015-11-09 12:42:37
Howard Roark: 2015-11-08 15:33:10

"You are given 3 integers a, b". That's 2 integers.

(Ruhan) => Done

Last edit: 2015-11-09 10:56:05
mehmetin: 2015-11-07 10:40:33

I think there aren't any big primes in the input, something of the order of 6 or 7 digits.

(Ruhan) => No, and I think I should add a big prime.

Last edit: 2015-11-07 18:23:41
Ruhan Habib: 2015-11-07 08:47:59

Hint: This problem has a quite small solution...

Last edit: 2015-11-07 08:48:12

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