Max (or near max) indexes should be tested for all bases, otherwise invalid solutions can pass, that don't check high enough primes (e.g. base 30, k = 150)

If you decided to use type annotations, please, be consistent and do it for the function return type as well.

The description must use "nonempty substring", instead of just "substring". If we allow an empty substring, we usually assume it's zero when converted to an integer, therefore no numbers satisfy the condition, because every number contains empty substring.

I think there should be code length limitation for the problem (to prevent hard-coding).