Given a range L to R, the task is to find the highest occurring digit in prime numbers which lie between L and R (both inclusive). If multiple digits have same highest frequency return the largest of them. If no prime number occurs between L and R, return -1.
 
Example 1:
Input: L = 2, R = 10
Output: 7
Explanation: Between 2 and 10 every digit
has same frquency and 7 is largest among
them.
Example 2:
Input: L = 2, R = 20
Output: 1
Explanation: Prime number between 2 and 20 are 
2, 3, 5, 7, 11, 13, 17, 19. 1 occur 
maximum i.e 5 times among 0 to 9.
Your Task:  
You dont need to read input or print anything. Complete the function maxDigit() which takes L and R as input parameter and returns the highest occuring digit. If multiple digits have same highest frequency return the largest of them. If no prime number occurs between L and R, return -1.
Expected Time Complexity: O(nlog(n)sqrt(n))
Expected Auxiliary Space: O(k)
Constraints:
1 <= L<= R <= 1000

Source: geeksforgeeks | Difficulty: EASY
Tags: Number theory

Starter code: #User function Template for python3

class Solution:

	def maxDigit(self, L, R):

		# code here



Solutions:
class Solution:

	def isprime(self, n):
		if n == 1:
			return False
		for i in range(2, int(n ** 0.5) + 1):
			if n % i == 0:
				return False
		return True

	def maxDigit(self, L, R):
		l = []
		for i in range(L, R + 1, 1):
			if self.isprime(i):
				c = i
				while c != 0:
					l.append(c % 10)
					c = c // 10
		l = sorted(l)
		a = 0
		b = 0
		for i in range(len(l) - 1, -1, -1):
			if l.count(l[i]) > a:
				a = l.count(l[i])
				b = l[i]
		if b == 0:
			return -1
		else:
			return b


import math

class Solution:

	def __init__(self):
		self.pl = self.primes()

	def primes(self):
		n = int(1000.0)
		pl = [True] * (n + 1)
		pl[0] = pl[1] = False
		lim = int(math.sqrt(n)) + 1
		for i in range(2, lim):
			for j in range(i * i, n + 1, i):
				if pl[i]:
					pl[j] = False
		res = [i for i in range(2, n + 1) if pl[i]]
		return res

	def bsf(self, arr, k):
		(l, h, idx) = (0, len(arr) - 1, -1)
		while l <= h:
			m = (l + h) // 2
			if arr[m] > k:
				h = m - 1
			else:
				idx = m
				l = m + 1
		return idx

	def bsc(self, arr, k):
		(l, h, idx) = (0, len(arr) - 1, -1)
		while l <= h:
			m = (l + h) // 2
			if arr[m] < k:
				l = m + 1
			else:
				idx = m
				h = m - 1
		return idx

	def maxDigit(self, L, R):
		x = self.bsc(self.pl, L)
		y = self.bsf(self.pl, R)
		d = {}
		for i in self.pl[x:y + 1]:
			while i != 0:
				if i % 10 in d:
					d[i % 10] += 1
				else:
					d[i % 10] = 1
				i = i // 10
		(me, m) = (-1, 0)
		for i in d:
			if d[i] >= m:
				(m, me) = (d[i], i)
		return me


class Solution:

	def maxDigit(self, M, N):
		product = 1
		mod = 10 ** 9 + 7
		table = {0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0}
		for j in range(M, N + 1):
			flag = True
			if j == 1:
				continue
			for i in range(2, int(j ** 0.5) + 1):
				if j % i == 0:
					flag = False
					break
			if flag:
				while j != 0:
					p = j % 10
					table[p] += 1
					j = j // 10
		digit = -1
		maxi = 1
		for j in table:
			if table[j] >= maxi:
				maxi = table[j]
				digit = j
		return digit


class Solution:

	def maxDigit(self, L, R):
		from collections import Counter
		n = R
		sieve = [True] * (n + 1)
		rec = Counter()
		for i in range(2, n + 1):
			if sieve[i]:
				for j in range(i * i, n + 1, i):
					sieve[j] = False
				if i >= L:
					for x in str(i):
						rec[x] += 1
		if not rec:
			return -1
		maxi = max(rec.values())
		if maxi == 0:
			return -1
		ans = '0'
		for (k, v) in rec.items():
			if v == maxi:
				ans = max(ans, k)
		return ord(ans) - ord('0')


import math

class Solution:

	def maxDigit(self, L, R):
		sieve = [0 for i in range(100000)]
		(sieve[0], sieve[1]) = (1, 1)
		for i in range(2, int(math.sqrt(100000)) + 1):
			if sieve[i] == 0:
				for j in range(i * i, 100000, i):
					sieve[j] = 1
		d = {i: 0 for i in range(10)}
		for i in range(L, R + 1):
			if sieve[i] == 0:
				data = i
				while data != 0:
					d[data % 10] += 1
					data //= 10
		(maxkey, maxval) = (float('-inf'), float('-inf'))
		for (key, val) in d.items():
			if val >= maxval:
				maxkey = key
				maxval = val
		if maxval == 0:
			return -1
		return maxkey


from math import sqrt

class Solution:

	def maxDigit(self, L, R):
		res = [0] * 10
		for i in range(L, R + 1):
			if self.findprimes(i):
				num = i
				while num != 0:
					rem = num % 10
					res[rem] += 1
					num = num // 10
		maxcount = 0
		maxi = -1
		for j in range(9, -1, -1):
			if maxcount < res[j]:
				maxcount = res[j]
				maxi = j
		return maxi

	def findprimes(self, N):
		if N <= 1:
			return 0
		for i in range(2, int(sqrt(N)) + 1):
			if N % i == 0:
				return 0
		return 1


import math

class Solution:

	def seive(self, n):
		primes = [True] * n
		primes[0] = primes[1] = False
		for i in range(4, n, 2):
			primes[i] = False
		x = int(math.sqrt(n)) + 1
		for i in range(3, x):
			for j in range(i * i, n, i):
				primes[j] = False
		ans = []
		for i in range(len(primes)):
			if primes[i]:
				ans.append(i)
		return ans

	def maxDigit(self, l, r):
		n = int(math.sqrt(r)) + 1
		primes = self.seive(n)
		arr = [True] * (r - l + 1)
		if l == 1:
			arr[0] = False
		for p in primes:
			base = l // p * p
			if base < l:
				base += p
			for i in range(base, r + 1, p):
				if i != p:
					arr[i - l] = False
		mp = {}
		mx = -999999
		val = -1
		for i in range(r - l + 1):
			if arr[i]:
				num = i + l
				while num > 0:
					k = num % 10
					if k in mp:
						mp[k] += 1
					else:
						mp[k] = 1
					if mp[k] >= mx:
						mx = mp[k]
						val = k
					num = num // 10
		return val


class Solution:

	def maxDigit(self, L, R):
		if L == 1:
			L = 3
		x = []
		for i in range(L, R + 1):
			c = 0
			for j in range(2, int(i ** 0.5) + 1):
				if i % j == 0:
					c = 1
					break
			if c == 0:
				x.append(i)
		a = ''
		for i in x:
			a += str(i)
		d = {}
		for i in a:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		ans = 0
		count = 0
		for i in d:
			if d[i] == count:
				if i > ans:
					ans = i
			if d[i] > count:
				ans = i
				count = d[i]
		if ans == 0:
			return -1
		return ans


class Solution:

	def maxDigit(self, L, R):
		l = []
		for x in range(max(2, L), R + 1):
			a = x
			for y in range(2, a):
				if a % y == 0:
					break
			else:
				l.append(a)
		if l == []:
			return -1
		dic = {}
		for x in range(10):
			dic[x] = 0
		for x in l:
			n = x
			while n > 0:
				z = n % 10
				dic[z] += 1
				n = n // 10
		mi = 0
		m = []
		for x in dic:
			if dic[x] > mi:
				m = []
				m.append(x)
				mi = dic[x]
			elif dic[x] == mi:
				m.append(x)
		if len(m) == 1:
			return m[0]
		else:
			return max(m)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(L, R) = input().split()
		L = int(L)
		R = int(R)
		ob = Solution()
		print(ob.maxDigit(L, R))


class Solution:

	def maxDigit(self, L, R):
		s = ''
		for i in range(L, R + 1):
			if i > 1:
				for j in range(2, int(i ** 0.5) + 1):
					if i % j == 0:
						break
				else:
					s += str(i)
		if s == '':
			return -1
		m = max(s.count('1'), s.count('2'), s.count('3'), s.count('4'), s.count('5'), s.count('6'), s.count('7'), s.count('8'), s.count('9'))
		if m == s.count('9'):
			return 9
		elif m == s.count('8'):
			return 8
		elif m == s.count('7'):
			return 7
		elif m == s.count('6'):
			return 6
		elif m == s.count('5'):
			return 5
		elif m == s.count('4'):
			return 4
		elif m == s.count('3'):
			return 3
		elif m == s.count('2'):
			return 2
		elif m == s.count('1'):
			return 1
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(L, R) = input().split()
		L = int(L)
		R = int(R)
		ob = Solution()
		print(ob.maxDigit(L, R))


class Solution:

	def maxDigit(self, L, R):
		p = []
		q = []
		r = []
		m = 0
		c1 = 0
		c3 = 0
		c5 = 0
		c7 = 0
		c9 = 0
		if L == 1:
			L = 2
		for i in range(L, R + 1):
			for j in range(2, int(i / 2) + 1):
				if i % j == 0:
					break
			else:
				p.append(i)
		if len(p) == 0:
			return -1
		q = [str(x) for x in p]
		s = ''
		for i in q:
			s += i
		m = max(s.count('1'), s.count('2'), s.count('3'), s.count('4'), s.count('5'), s.count('6'), s.count('7'), s.count('8'), s.count('9'))
		if m == s.count('9'):
			return 9
		elif m == s.count('8'):
			return 8
		elif m == s.count('7'):
			return 7
		elif m == s.count('6'):
			return 6
		elif m == s.count('5'):
			return 5
		elif m == s.count('4'):
			return 4
		elif m == s.count('3'):
			return 3
		elif m == s.count('2'):
			return 2
		elif m == s.count('1'):
			return 1


class Solution:

	def primeCheck(self, n):
		check = True
		for i in range(2, n):
			if n % i == 0:
				check = False
				break
		return check

	def primeListGetter(self, rangeValue1, rangeValue2):
		resultList = []
		for val in range(rangeValue1, rangeValue2 + 1):
			if self.primeCheck(val) and val != 1:
				resultList.append(val)
		return resultList

	def maxDigit(self, L, R):
		primeList = self.primeListGetter(L, R)
		if len(primeList) == 0:
			return -1
		frequency = {}
		maxValueCheck = 0
		maxValueIndex = 0
		for val in primeList:
			charVal = str(val)
			for key in charVal:
				key = int(key)
				frequency[key] = frequency.get(key, 0) + 1
		values = list(frequency.values())
		keys = list(frequency.keys())
		if int(sum(values) / len(values)) == values[0]:
			return max(keys)
		else:
			maximumValue = max(values)
			maximumKey = keys[0]
			for i in keys:
				if frequency[i] == maximumValue:
					if maximumValue <= frequency[i]:
						maximumKey = i
			return maximumKey


class Solution:

	def isPrime(self, n):
		if n == 1:
			return False
		for i in range(2, n):
			if n % i == 0:
				return False
		return True

	def maxDigit(self, L, R):
		digitCount = [0 for i in range(10)]
		for i in range(L, R + 1):
			if self.isPrime(i):
				digitCount[i % 10] += 1
				if i >= 10:
					digitCount[i % 100 // 10] += 1
				if i >= 100:
					digitCount[i // 100] += 1
		maxDigit = -1
		maxCount = 0
		for i in range(9, -1, -1):
			if digitCount[i] > maxCount:
				maxCount = digitCount[i]
				maxDigit = i
		return maxDigit


from collections import Counter

def isprime(x):
	if x <= 1:
		return 0
	if x == 2:
		return 1
	else:
		for i in range(2, x):
			if x % i == 0:
				return 0
		return 1

class Solution:

	def maxDigit(self, L, R):
		l = []
		for i in range(L, R + 1):
			if isprime(i):
				l.append(i)
		if l:
			l = [str(x) for x in l]
			res = ''
			res = ''.join(l)
			k = list(res)
			m = Counter(k)
			p = []
			for (keys, values) in m.items():
				p.append(values)
			d = max(p)
			res1 = []
			for (keys, values) in m.items():
				if d == values:
					res1.append(keys)
			if res1:
				return max(res1)
			else:
				return -1
		else:
			return -1


from collections import defaultdict
from math import ceil

class Solution:

	def maxDigit(self, L, R):
		primes = []
		count = defaultdict(int)

		def prime(n):
			not_primes = set()
			for i in range(3, ceil(n / 2) + 1, 2):
				for j in range(3 * i, n, 2 * i):
					not_primes.add(j)
			return not_primes
		if L <= 2 <= R:
			primes.append(2)
		not_primes = prime(R + 1)
		not_primes.add(1)
		for i in range(L, R + 1):
			if i % 2 == 1 and i not in not_primes:
				primes.append(i)
		(ans, mmax) = ('', 0)
		for num in primes:
			for c in str(num):
				count[c] += 1
				if count[c] > mmax:
					(mmax, ans) = (count[c], c)
				elif count[c] == mmax:
					if c > ans:
						ans = c
		return int(ans) if ans != '' else -1


import math

class Solution:

	def maxDigit(self, L, R):
		l = 1001
		ans = [0] * l
		ans[1] = 0
		ans[0] = 1
		for i in range(2, int(math.sqrt(l)) + 1):
			if ans[i] == 0:
				for j in range(2 * i, l, i):
					ans[j] = 1
		let = [0] * 10
		for i in range(L, R + 1):
			if ans[i] == 0:
				t = i
				digit = 0
				while t != 0:
					digit = t % 10
					let[digit] += 1
					t //= 10
		m = let[0]
		ans = 0
		for j in range(1, 10):
			if m <= let[j]:
				m = let[j]
				ans = j
		if m == 0:
			return -1
		return ans


class Solution:

	def maxDigit(self, L, R):
		l = []
		max = 0
		for i in range(L, R + 1):
			if i >= 1:
				for j in range(2, i):
					if i % j == 0:
						break
				else:
					l.append(str(i))
		if len(l) == 0:
			return -1
		k = ''.join(l)
		for i in range(1, 10):
			if k.count(str(i)) >= max:
				max = k.count(str(i))
				a = i
		return a


import math as m

class Solution:

	def maxDigit(self, L, R):

		def IsPrime(n):
			if n == 1:
				return True
			for i in range(2, int(m.sqrt(n)) + 1):
				if n % i == 0:
					return False
			return True
		s = ''
		for i in range(L, R + 1):
			if IsPrime(i):
				s += str(i)
		if len(s) == 0:
			return -1
		s = list(s)
		l = list(set(s))
		l.sort(key=int)
		maxi = 0
		for i in l:
			sc = s.count(i)
			if sc >= maxi:
				maxi = sc
				st = i
		return st


import math

class Solution:

	def prime(self, n):
		if n == 0:
			return False
		if n == 2 or n == 3 or n == 1:
			return True
		if n % 2 == 0 or n % 3 == 0:
			return False
		for i in range(5, int(math.sqrt(n)) + 1, 6):
			if n % i == 0 or n % (i + 2) == 0:
				return False
		return True

	def maxDigit(self, l, r):
		c = []
		nivas = []
		ni = 0
		for i in range(l, r + 1):
			if self.prime(i):
				ni += 1
				for j in str(i):
					c.append(j)
					nivas.append(int(j))
		if ni == len(nivas) and ni > 0:
			return max(nivas)
		if ni == 0:
			return '-1'
		d = {}
		for i in c:
			if i not in d.keys():
				d[i] = 1
			else:
				d[i] += 1
		a = max(d, key=d.get)
		if ni > 0:
			return a


import math as m

class Solution:

	def maxDigit(self, L, R):
		s = ''
		d = {}
		x = ''
		maxi = 0

		def pr(n):
			if n == 1:
				return True
			if n == 0:
				return False
			else:
				for i in range(2, int(m.sqrt(n) + 1)):
					if n % i == 0:
						return False
				return True
		for k in range(L, R + 1):
			if pr(k):
				s = s + str(k)
		if len(s) == 0:
			return -1
		for i in s:
			d[i] = d.get(i, 0) + 1
		for i in d:
			if d[i] > maxi:
				maxi = d[i]
		for i in d:
			if d[i] >= maxi:
				if i > x:
					x = i
					maxi = d[i]
		return x


class Solution:

	def maxDigit(self, L, R):
		n = 1001
		seive = []
		for _ in range(n + 1):
			seive.append(1)
		seive[0] = 0
		seive[1] = 1
		for i in range(2, n + 1):
			if seive[i] == 1:
				j = i * i
				while j <= n:
					seive[j] = 0
					j += i
		l = []
		for i in range(L, R + 1):
			if seive[i] == 1:
				l.append(i)
		d = dict()
		for word in l:
			s = str(word)
			s = list(s)
			for i in s:
				d[int(i)] = d.get(int(i), 0) + 1
		val = -1
		for (k, v) in sorted(d.items(), key=lambda item: item[1], reverse=True):
			val = v
			break
		res = []
		for (k, v) in sorted(d.items()):
			if v == val:
				res.append(k)
		if len(res) == 0:
			return -1
		return max(res)


class Solution:

	def maxDigit(self, L, R):

		def findPrime(L, R):
			primes = []
			for i in range(L, R + 1):
				for j in range(2, i // 2 + 1):
					if i % j == 0:
						break
				else:
					primes.append(i)
			return primes
		primes = findPrime(L, R)
		if not primes:
			return -1
		d = {}
		for p in primes:
			str_p = str(p)
			for digit in str_p:
				digit = int(digit)
				if digit in d:
					d[digit] += 1
				else:
					d[digit] = 1
		digits_freq = list(d.items())
		digits_freq.sort(key=lambda x: (x[1], x[0]), reverse=True)
		return digits_freq[0][0]


class Solution:

	def maxDigit(self, L, R):
		c = [True] * (R + 1)
		p = 2
		b = L // 2
		while p * p <= R:
			if c[p] == True:
				for i in range(p * b, R + 1, p):
					if i != p:
						c[i] = False
			p = p + 1
			b = L // p
		m = {}
		for i in range(L, len(c)):
			if c[i] == True:
				while i > 0:
					a = i % 10
					if a in m:
						m[a] = m[a] + 1
					else:
						m[a] = 1
					i = i // 10
		if len(m) == 0:
			return -1
		a = max(m.values())
		if a == 1:
			return max(m.keys())
		r = []
		for keys in m:
			if m[keys] == a:
				r.append(keys)
		return max(r)