For any two given positive integers p and q, find (if present) the leftmost digit in the number obtained by computing the exponent p^{q}  i.e. p raised to the power q, such that it is a divisor of p^{q}.
Note: p^{q}^{ }may be a very huge number, so if the number of digits in p^{q} is greater than 18, you need to extract the first 10 digits of the result and  check if any digit of that number divides the number.
Example 1:
Input: p = 1, q = 1
Output: 1 
Explanation: 1 raised to the power 1 gives 1, 
which is a divisor of itself i.e. 1.  
Example 2:
Input: p = 5, q = 2
Output: 5
Explanation: The exponent 5 raised to the power 2 
gives 25, wherein leftmost digit 2, does not 
divide 25 but 5 does. Hence output is 5. 
Your Task:  
You dont need to read input or print anything. Complete the function leftMostDiv() which takes p and q as input parameter and returns the left-most digit in the number p^{q} which is a divisor of p^{q}. If no such digit exists, returns -1.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)
Constraints:
1 <= p , q <=50

Difficulty: MEDIUM
Tags: Number theory
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3
class Solution:
	def leftMostDiv(self, p, q):
		# code here


Solutions:
class Solution:

	def leftMostDiv(self, p, q):
		e = p ** q
		if len(str(e)) > 18:
			e = str(e)[0:10]
		for i in str(e):
			if i != '0':
				if int(e) % int(i) == 0:
					return int(i)
		return -1


class Solution:

	def leftMostDiv(self, p, q):
		a = p ** q
		s = str(a)
		if len(s) > 18:
			s = s[0:10]
		a = int(s)
		for i in s:
			d = int(i)
			if d == 0:
				continue
			if a % d == 0:
				return i
		return -1


class Solution:

	def leftMostDiv(self, p, q):
		g = p ** q
		h = str(g)
		n = len(h)
		if n > 18:
			h = h[:10]
		g = int(h)
		for i in h:
			if i != '0' and g % int(i) == 0:
				return i
		return -1


class Solution:

	def leftMostDiv(self, p, q):
		x = p ** q
		z = str(x)
		if len(z) > 18:
			z = z[:10]
		d = int(z)
		for i in z:
			y = int(i)
			if y != 0 and d % y == 0:
				return y
		return -1
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(p, q) = input().split()
		p = int(p)
		q = int(q)
		ob = Solution()
		print(ob.leftMostDiv(p, q))


class Solution:

	def leftMostDiv(self, p, q):
		x = p ** q
		z = str(x)
		if len(z) > 18:
			z = z[:10]
		d = int(z)
		for i in z:
			y = int(i)
			if y != 0 and d % y == 0:
				return y
		return -1


class Solution:

	def leftMostDiv(self, p, q):
		n = str(p ** q)
		l = len(n)
		if l > 18:
			n = n[0:10]
			l = 10
		for i in range(l):
			if n[i] != '0' and int(n) % int(n[i]) == 0:
				return int(n[i])
		return -1


class Solution:

	def leftMostDiv(self, p, q):
		res = 1
		while q != 0:
			res *= p
			q -= 1
		l = list(str(res))
		if len(l) > 18:
			l = l[:10]
			res = int(''.join(l))
		for i in l:
			if int(i) != 0 and res % int(i) == 0:
				return int(i)
		return -1


class Solution:

	def leftMostDiv(self, p, q):
		if p ** q // 10 ** 18 > 0:
			d = len(str(p ** q))
			number = p ** q // 10 ** (d - 10)
		else:
			number = p ** q
		divisor = str(number)
		ans = -1
		for i in range(len(divisor)):
			try:
				if number % int(divisor[i]) == 0:
					ans = int(divisor[i])
					break
			except:
				pass
		return ans