A number y is said to be the k-th power of a number x if y = x^k, i.e., y is the product of k copies of x.
You are given two Strings left and right. Return the greatest k such that there is an integer y (left <= y <= right) such that y is the k-th power of some integer x.
|-||left will be an integer between 2 and 10^12, inclusive, without extra leading zeroes.|
|-||right will be an integer between left and 10^12, inclusive, without extra leading zeroes.|