#2642 BigFatInteger

2 s   64 MB  

Description

This problem statement contains superscipts that may not display properly outside the applet.


Lun the dog loves very large integers. Her favorite is $A^B$ ($A$ to the power of $B$).

She has an integer variable $X$. Initially, the value of $X$ is set to 1. She can perform the following two kinds of operations in any order, any number of times.
  • Operation 1: choose a prime number $p$, then multiply $X$ by $p$.
  • Operation 2: choose a positive divisor d of the value of $X$ at that point, then multiply $X$ by $d$.

 

Input

You are given two ints $A$ and $B$

$A$ will be between $2$ and $1,000,000$ ($10^6$), inclusive.

$B$ will be between $1$ and $1,000,000$ ($10^6$), inclusive.

Output

Return the minimum number of operations Lun needs to perform in order to obtain $X$ = $A^B$ from the initial state $X = 1$.

Sample Input

Sample Output

360 8
8

Source

Topcoder SRM 599 Div1