Practice Primes and Arithmetic with the exercise "Divide the factorial"

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Primes
Arithmetic

Statement

Goal

Given two integers A and B, you have to find the largest power of A that divides B! with no remainder.
You have to find the largest integer value of X such that A^X divides B! where B! = B × (B-1) × (B-2) × … × 2 × 1.

Input

One line containing A and B, separated by a single space.

Output

A single line containing X, the largest power of A that divides B!

Constraints

2 ≤ A, B ≤ 10^7

Example

Input

7 14

Output

Solve it

A higher resolution is required to access the IDE