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 Output

360 8

8


## Source

Topcoder SRM 599 Div1