Background

大王要挑战一只强悍的怪兽，怪兽有 H 点初始血量，还带着 k 点特殊护甲。这护甲的诡异之处在于，大王每次攻击的实际伤害，等于当前攻击次数（从 1 开始计数）与护甲值 k 的最大公约数。为了尽快结束战斗、守护家园，大王需要算出最少多少次攻击才能让怪兽血量≤0，彻底击败它！

Description

给定两个整数 H（怪兽初始血量）和 k（怪兽护甲值），计算最少需要多少次攻击才能让怪兽血量≤0。每次攻击的伤害为当前攻击次数与 k 的最大公约数（攻击次数从 1 开始递增）

Format

Input

两个整数 H 和 k，满足 $1 \leq H \leq 10^6$，$1 \leq k \leq 10^5$。

Output

一个整数，表示最少攻击次数。

Samples

10 6

6

Limitation

1s, 1024KiB for each test case.