What is my exponential potential? We'll define the N-exponential potential of a positive integer M as the count of prefixes of MN that are perfect N-powers.

The prefixes of an integer are all the contiguous subsequences of digits that start with the first one, interpreted as numbers in base 10. For example, the prefixes of 2744 are 2, 27, 274 and 2744.

A prefix P is a perfect N-power if there exists an integer K such that KN = P. For example, 81 is a perfect 4-power because 34 = 81.



Given two strictly positive integers M and N, compute the N-exponential potential of M according to the definition above.

For instance, the 2-exponential potential of 13 is 3 because 132 is 169, and 1, 16 and 169 are all perfect squares.

Test cases

Naturally, the outputs will nearly always be pretty small because powers are... well... exponentially growing functions and having multiple perfect-power prefixes is rather rare.

M, N     -&gt; Output

8499, 2  -&gt; 1
4,    10 -&gt; 2
5,    9  -&gt; 2
6,    9  -&gt; 2
13,   2  -&gt; 3
Brachylog, 12 bytes

{^a₀.&amp;b~b^}ᶜ


Try it online!

Explanation

{^a₀.&amp;b~b^}ᶜ
{         }ᶜ  Count the number of ways the following can succeed:
  a₀            A prefix of
 ^                the first {input} to the power of the second {input}
    .&amp;          produces the same output with the same input as
       ~b         any number
         ^        to the power of
      b           all inputs but the first (i.e. the second input)