For any integer k > 0, an integer n is a kth power if there exists an integer a such that a^k = n. Furthermore, n > 1 is a nontrivial power if it is a kth power for some integer k > 1. Show how to determine whether a given β-bit integer n is a nontrivial power in time polynomial in β.