Monic irreducible polynomials P64196

Here, we consider polynomials in $\mathbb{F}_p[x]$, that is, polynomials on $x$ whose coefficients are elements of $\mathbb{F}_p=\{0, 1, 2, \ldots, p-1\}$, where $p$ is a prime number.

A polynomial is monic if the coefficient of its term with largest degree is $1$. A polynomial is irreducible if it cannot be written as the product of two polynomials of smaller degree. Your task is to count the number of monic, irreducible polynomials of $\mathbb{F}_p[x]$ of a given degree $d$.

Too difficult? Do not despair! The problem is not so hard, once you know that, in $\mathbb{F}_p[x]$, every monic polynomial can be written in a unique way as a factor of monic, irreducible polynomials. For instance, in $\mathbb{F}_2[x]$ there are $4$ monic polynomials of degree $2$ (in $\mathbb{F}_2[x]$, all polynomials are monic), but only one of them is irreducible: $$x^2 = x\cdot x \qquad \enspace x^2+1 = (x+1)\cdot(x+1) \qquad \enspace x^2+x = x\cdot (x+1) \qquad \enspace x^2+x+1 = \enspace ???$$

In $\mathbb{F}_2[x]$, there are $8$ monic polynomials of degree $3$, but only two of them are irreducible: $$\begin{align*} x^3 &= x\cdot x \cdot x \enspace & \enspace x^3 + x^2 &= x\cdot x\cdot (x+1) \\ x^3+1 &= (x+1)\cdot(x^2+x+1) \enspace & \enspace x^3+x^2+1 &= \enspace ??? \\ x^3 + x &= x\cdot (x+1)\cdot (x+1) \enspace & \enspace x^3 + x^2 + x &= x\cdot (x^2+x+1) \\ x^3+x+1 &= \enspace ??? \enspace & \enspace x^3+x^2+x+1 &= (x+1)\cdot(x+1)\cdot(x+1) \end{align*}$$

Input

Input consists of several cases, each with a prime number $2 \le p \le 30$ and an integer number $2 \le d \le 30$. Additionally, we have $p^d < 10^9$.

Output

For every case, print the number of monic, irreducible polynomials in $\mathbb{F}_p[x]$ of degree $d$.