Given a string str you have to answer several queries on that string. In each query you will be provided two values L and R and you have to find the number of distinct characters in the sub string from index L to index R (inclusive) of the original string.
 
Example 1:
Input: str = "abcbaed",
Query = {{1,4},{2,4},{1,7}}
Output: {3,2,5}
Explanation: For the first query distinct 
characters from [1, 4] are a, b and c.
For the second query distinct characters from
[2, 4] are b and c.
For the third query distinct characters from
[1, 7] are a, b, c, d and e.
 
Your Task:
You don't need to read or print anyhting. Your task is to complete the function SolveQueries() which takes str and Query as input parameter and returns a list containing answer for each query.
 
Expected Time Complexity: O(max(26*length of str, 26 * No of queries))
Expected Space Complexity: O(26 * length of str)
 
Constraints:
1 <= |str| <= 10^{5}
1 <= No of Queries <= 10^{4}
1 <= L_{i} <= R_{i} <= |str|

Difficulty: MEDIUM
Tags: Dynamic programming
Skill types: Dynamic programming
Expected Time Complexity: O(max(26*length of str, 26 * No of queries))
Expected Auxiliary Space: O(26 * length of str)

Starter code:
#User function Template for python3



class Solution:

	def SolveQueris(self, str, Query):

		# Code here

Solutions:
class Solution:

	def SolveQueris(self, str, Query):
		res = []
		for Pair in Query:
			s = set()
			string = str[Pair[0] - 1:Pair[1]]
			for i in string:
				if i not in s:
					s.add(i)
			res.append(len(s))
		return res


class Solution:

	def SolveQueris(self, str, Query):
		res = []
		for i in Query:
			count = [0] * 26
			c = 0
			for j in range(i[0] - 1, i[1]):
				if count[ord(str[j]) - ord('a')] == 0:
					c += 1
				count[ord(str[j]) - ord('a')] += 1
			res.append(c)
		return res


class Solution:

	def SolveQueris(self, s, q):
		s = list(s)
		c = []
		for i in q:
			(a, b) = (i[0], i[1])
			c.append(len(set(s[a - 1:b])))
		return c


class Solution:

	def SolveQueris(self, str, Query):
		combined = []
		for i in Query:
			each = self.find_distinct(str, i[0] - 1, i[1])
			combined.append(each)
		return combined

	def find_distinct(self, str, start, stop):
		set1 = set()
		for i in str[start:stop]:
			set1.add(i)
		return len(set1)


class Solution:

	def SolveQueris(self, str, Query):
		p = len(str)
		q = len(Query)
		f = ord(str[0]) - 97
		a = [[0 for i in range(26)] for j in range(max(p, q))]
		a[0][ord(str[0]) - 97] = 1
		for i in range(1, max(p, q)):
			a[i] = a[i - 1].copy()
			if i < p:
				a[i][ord(str[i]) - 97] = a[i - 1][ord(str[i]) - 97] + 1
		b = []
		for (i, j) in Query:
			c = 0
			for k in range(26):
				if a[j - 1][k] != a[i - 1][k] or (i == 1 and k == f):
					c += 1
				elif i != 1 and a[i - 1][k] != a[i - 2][k]:
					c += 1
			b.append(c)
		return b


class Solution:

	def SolveQueris(self, str, Query):
		res = []
		for (s, e) in Query:
			res.append(len(set(list(str[s - 1:e]))))
		return res


class Solution:

	def SolveQueris(self, str, Query):
		S = str
		ans = []
		for i in range(0, len(Query)):
			sets = set(S[Query[i][0] - 1:Query[i][1]])
			ans.append(len(sets))
		return ans


from copy import copy

class Solution:

	def SolveQueris(self, str, Query):
		n = len(str)
		records = [[0] * 26 for _ in range(n + 1)]
		for i in range(n):
			idx = ord(str[i]) - ord('a')
			records[i + 1] = records[i].copy()
			records[i + 1][idx] += 1
		ans = []
		for (s, e) in Query:
			cnt = sum((x1 - x0 > 0 for (x1, x0) in zip(records[e], records[s - 1])))
			ans.append(cnt)
		return ans


class Solution:

	def SolveQueris(self, str, Query):
		a = []
		for i in Query:
			x = i[0] - 1
			y = i[1] - 1
			res = str[x:y + 1]
			top = len(list(set(list(res))))
			a.append(top)
		return a


class Solution:

	def SolveQueris(self, S, Query):
		N = len(S)
		dp = [[0 for i in range(26)] for i in range(N + 1)]
		for i in range(N):
			for j in range(26):
				dp[i + 1][j] = dp[i][j]
			dp[i + 1][ord(S[i]) - ord('a')] += 1
		ans = []
		for (l, r) in Query:
			c = 0
			for i in range(26):
				if dp[r][i] - dp[l - 1][i] > 0:
					c += 1
			ans.append(c)
		return ans


class Solution:

	def SolveQueris(self, str, Query):
		ans = []
		for i in Query:
			s = set(str[i[0] - 1:i[1]])
			ans.append(len(s))
		return ans


class Solution:

	def SolveQueris(self, str, Query):
		l = []
		for i in Query:
			x = str[i[0] - 1:i[1]]
			l.append(x)
		x = []
		for i in l:
			s = ''
			for j in i:
				if j not in s:
					s += j
			x.append(len(s))
		return x


class Solution:

	def SolveQueris(self, str, Query):
		d = []
		ans = []
		for i in range(len(str)):
			p = []
			d.append(p)
		d1 = [0] * 26
		for i in range(len(str)):
			p = ord(str[i]) - 97
			d1[p] += 1
			h = d1.copy()
			d[i] = h
		for x in Query:
			l = x[0] - 1
			r = x[1] - 1
			c = 0
			for i in range(26):
				if d[r][i] - d[l][i] > 0 or i == ord(str[l]) - 97:
					c += 1
			ans.append(c)
		return ans
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		str = input()
		q = int(input())
		Query = []
		for i in range(q):
			a = list(map(int, input().split()))
			Query.append(a)
		obj = Solution()
		ans = obj.SolveQueris(str, Query)
		for _ in ans:
			print(_, end=' ')
		print()


class Solution:

	def SolveQueris(self, str, Query):
		arr = [[0 for i in range(26)] for j in range(len(str) + 1)]
		for i in range(len(str)):
			ind = ord(str[i]) - 97
			arr[i + 1][ind] = 1
			for j in range(26):
				arr[i + 1][j] += arr[i][j]
		ans = []
		for q in Query:
			(a, b) = (q[0], q[1])
			total = 0
			for j in range(26):
				total += 1 if arr[b][j] - arr[a - 1][j] > 0 else 0
			ans.append(total)
		return ans
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		str = input()
		q = int(input())
		Query = []
		for i in range(q):
			a = list(map(int, input().split()))
			Query.append(a)
		obj = Solution()
		ans = obj.SolveQueris(str, Query)
		for _ in ans:
			print(_, end=' ')
		print()


from copy import copy

class Solution:

	def SolveQueris(self, str, Query):
		n = len(str)
		records = [[0] * 26 for _ in range(n + 1)]
		for i in range(n):
			idx = ord(str[i]) - ord('a')
			records[i + 1] = records[i].copy()
			records[i + 1][idx] += 1
		ans = []
		for (s, e) in Query:
			cnt = sum((x1 - x0 > 0 for (x1, x0) in zip(records[e], records[s - 1])))
			ans.append(cnt)
		return ans
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		str = input()
		q = int(input())
		Query = []
		for i in range(q):
			a = list(map(int, input().split()))
			Query.append(a)
		obj = Solution()
		ans = obj.SolveQueris(str, Query)
		for _ in ans:
			print(_, end=' ')
		print()


class Solution:

	def SolveQueris(self, str, Query):
		ans = []
		for element in Query:
			temp = str[element[0] - 1:element[1]]
			dicti = {}
			count = 0
			for i in temp:
				if not i in dicti:
					count += 1
					dicti[i] = 1
			ans.append(count)
		return ans


class Solution:

	def SolveQueris(self, str, Query):
		result = []
		for q in Query:
			subquery = str[q[0] - 1:q[1]]
			result.append(len(set(subquery)))
		return result


class Solution:

	def SolveQueris(self, str, Query):
		a = []
		for i in Query:
			b = []
			c = 0
			for j in range(i[0] - 1, i[1]):
				if str[j] not in b:
					b.append(str[j])
					c += 1
			a.append(c)
		return a


class Solution:

	def SolveQueris(self, string, Query):
		dp = [['' for i in range(len(string))] for j in range(len(string))]
		for i in range(len(string)):
			dp[i][i] = string[i]
		for i in range(len(string) - 1):
			for j in range(i + 1, len(string)):
				dp[i][j] = dp[i][j - 1] + (string[j] if string[j] not in dp[i][j - 1] else '')
		ans = []
		for item in Query:
			ans.append(len(dp[item[0] - 1][item[1] - 1]))
		return ans


class Solution:

	def SolveQueris(self, str, Query):
		res = []
		for i in range(len(Query)):
			T = [False] * 26
			counter = 0
			for j in range(Query[i][0] - 1, Query[i][1]):
				if T[ord(str[j]) - ord('a')] == False:
					counter += 1
					T[ord(str[j]) - ord('a')] = True
			res.append(counter)
		return res


class Solution:

	def SolveQueris(self, str, Query):
		res = []
		for queryi in Query:
			(left, right) = (queryi[0], queryi[1])
			tmp = set()
			for i in range(left - 1, right):
				tmp.add(str[i])
			res.append(len(tmp))
		return res


class Solution:

	def SolveQueris(self, str, Query):
		don = []
		for query in Query:
			l = query[0]
			r = query[1]
			arr = str[l - 1:r]
			don.append(len(set(arr)))
		return don


class Solution:

	def SolveQueris(self, s, Q):
		l1 = []
		for i in Q:
			(j, k) = i
			x = set(list(s[j - 1:k]))
			l1.append(len(x))
		return l1


class Solution:

	def SolveQueris(self, str, Query):
		lst = []
		for i in Query:
			myDict = {}
			lst.append(self.fun(str, i[0] - 1, i[1] - 1, myDict))
		return lst

	def fun(self, str, l, r, myDict):
		if l == r:
			if str[l] not in myDict:
				return 1
			else:
				return 0
		if str[r] not in myDict:
			myDict[str[r]] = 1
			return 1 + self.fun(str, l, r - 1, myDict)
		return self.fun(str, l, r - 1, myDict)


class Solution:

	def SolveQueris(self, str, Query):
		ans = []
		for i in Query:
			arr = []
			count = 0
			for j in range(i[0] - 1, i[1]):
				if str[j] in arr:
					pass
				else:
					arr.append(str[j])
					count += 1
			ans.append(count)
		return ans


class Solution:

	def SolveQueris(self, str, Query):
		tmp_list = []
		for i in range(len(Query)):
			tmp_list.append(len(set(str[Query[i][0] - 1:Query[i][1]])))
		return tmp_list


from collections import defaultdict

class Solution:

	def SolveQueris(self, str, Query):
		dp = [[0 for _ in range(26)] for _ in range(len(str) + 1)]
		for i in range(len(str)):
			for j in range(26):
				dp[i + 1][j] = dp[i][j]
				if ord(str[i]) - 97 == j:
					dp[i + 1][j] += 1
		ans = []
		for k in range(len(Query)):
			l = Query[k][0]
			r = Query[k][1]
			cur = 0
			for j in range(0, 26):
				if dp[r][j] - dp[l - 1][j] > 0:
					cur += 1
			ans.append(cur)
		return ans


class Solution:

	def SolveQueris(self, str, Query):
		res = []
		for m in Query:
			i = m[0] - 1
			j = m[1]
			res.append(len(set(str[i:j])))
		return res


class Solution:

	def SolveQueris(self, s, Query):
		lt = []
		for i in Query:
			h = s[i[0] - 1:i[1]]
			f = set(h)
			lt.append(len(f))
		return lt


class Solution:

	def SolveQueris(self, str, Query):
		res = []
		for i in Query:
			countdistinct = helper(str, i[0] - 1, i[1])
			res.append(countdistinct)
		return res

def helper(str, i, j):
	dis = set()
	for a in str[i:j]:
		dis.add(a)
	return len(dis)


class Solution:

	def SolveQueris(self, str, Query):
		return [len(set(str[q[0] - 1:q[1]])) for q in Query]


class Solution:

	def SolveQueris(self, str, Query):
		lst = []
		for i in Query:
			L = i[0]
			R = i[1]
			lst1 = []
			for i in range(L, R + 1):
				if str[i - 1] not in lst1:
					lst1.append(str[i - 1])
			lst.append(len(lst1))
		return lst


class Solution:

	def SolveQueris(self, str, Query):
		res = []
		for i in Query:
			substr = str[i[0] - 1:i[1]]
			c = len(set(substr))
			res.append(c)
		return res


class Solution:

	def SolveQueris(self, strs, query):
		ans = []
		s = ''
		for i in range(len(query)):
			x = query[i][0]
			y = query[i][1]
			s = strs[x - 1:y]
			ans.append(len(set(s)))
		return ans


class Solution:

	def SolveQueris(self, str, Query):
		result = []
		d = {}
		for i in Query:
			for j in str[i[0] - 1:i[1]]:
				if j not in d:
					d[j] = 1
				else:
					d[j] += 1
			result.append(len(d))
			d.clear()
		return result


class Solution:

	def SolveQueris(self, str, Query):
		result = []
		for i in Query:
			result.append(len(set(str[i[0] - 1:i[1]])))
		return result


class Solution:

	def SolveQueris(self, s, q):
		p = []
		l = [0] * 26
		for i in range(len(s)):
			l[ord(s[i]) - 97] += 1
			p.append(l.copy())
		ans = []
		for (i, j) in q:
			c = 0
			for z in range(26):
				if i == 1:
					if p[j - 1][z] > 0:
						c += 1
				elif p[j - 1][z] - p[i - 2][z] > 0:
					c += 1
			ans.append(c)
		return ans


class Solution:

	def SolveQueris(self, str, Query):
		result = []
		for (L, R) in Query:
			d = {}
			for i in range(L - 1, R):
				if str[i] not in d:
					d[str[i]] = 1
				else:
					d[str[i]] += 1
			result.append(len(d))
		return result


class Solution:

	def SolveQueris(self, str, Query):
		x = []
		for i in Query:
			y = str[i[0] - 1:i[1]]
			x.append(len(set(y)))
		return x


class Solution:

	def SolveQueris(self, str, Query):
		n = len(str)
		dp = [[0] * 26 for ele in range(n + 1)]
		for i in range(n):
			for j in range(26):
				dp[i + 1][j] = dp[i][j]
			dp[i + 1][ord(str[i]) - 97] = dp[i][ord(str[i]) - 97] + 1
		ans = []
		for (s, e) in Query:
			count = 0
			for i in range(26):
				if dp[e][i] - dp[s - 1][i] > 0:
					count += 1
			ans.append(count)
		return ans


class Solution:

	def SolveQueris(self, string, Query):
		lst = []
		for q in Query:
			l = q[0] - 1
			r = q[1]
			if l < 0:
				l = 0
			if r > len(string):
				r = len(string)
			s = set()
			for char in string[l:r]:
				s.add(char)
			n = len(s)
			lst.append(n)
		return lst


class Solution:

	def SolveQueris(self, s, query):
		ans = []
		for (i, j) in query:
			ans.append(len(set(s[i - 1:j])))
		return ans


class Solution:

	def SolveQueris(self, s, query):
		ans = []
		for (i, j) in query:
			hashmap = {}
			count = 0
			for x in s[i - 1:j]:
				if hashmap.get(x) == None:
					hashmap[x] = 1
					count += 1
			ans.append(count)
		return ans


import collections

class Solution:

	def SolveQueris(self, str, Query):
		idx = {}
		visited = collections.defaultdict(int)
		for (index, val) in enumerate(str):
			visited[val] += 1
			idx[index + 1] = dict(visited)
		ans = []
		for (i, j) in Query:
			if i - 1 >= 1:
				temp1 = dict(idx[j])
				temp2 = idx[i - 1]
				for (key, val) in temp2.items():
					if key in temp1:
						temp1[key] -= val
						if temp1[key] <= 0:
							del temp1[key]
				ans.append(len(temp1))
			else:
				ans.append(len(idx[j]))
		return ans


class Solution:

	def SolveQueris(self, str, Query):
		out = []
		for [i, j] in Query:
			out.append(len(set(str[i - 1:j])))
		return out


class Solution:

	def SolveQueris(self, str, Query):
		res = []
		for i in Query:
			l = i[0]
			r = i[1]
			t = str[l - 1:r]
			s = set(t)
			res.append(len(s))
		return res


class Solution:

	def SolveQueris(self, s, Query):
		n = len(s)
		dp = [[0 for i in range(n)] for j in range(n)]
		for i in range(n):
			f = dict()
			for j in range(i, n):
				if s[j] not in f:
					f[s[j]] = 1
				dp[i][j] = len(f)
		ans = []
		for q in Query:
			(l, r) = (q[0], q[1])
			ans.append(dp[l - 1][r - 1])
		return ans


class Solution:

	def SolveQueris(self, str1, l):
		l1 = []
		s1 = ''
		for i in range(len(l)):
			for j in range(l[i][0] - 1, l[i][1]):
				if str1[j] not in s1:
					s1 += str1[j]
			l1.append(len(s1))
			s1 = ''
		return l1


class Solution:

	def SolveQueris(self, s, queries):
		letters = [ord(c) - 97 for c in s]
		n = len(letters)
		counts = []
		counts.append([0] * 26)
		for i in range(n):
			c = letters[i]
			current = counts[i][:]
			current[c] += 1
			counts.append(current)
		result = []
		for q in queries:
			start = q[0]
			end = q[1]
			count = 0
			for i in range(26):
				if counts[end][i] == counts[start - 1][i]:
					count += 1
			result.append(26 - count)
		return result


class Solution:

	def SolveQueris(self, s, Query):
		res = []
		for q in Query:
			(l, r) = q
			l -= 1
			res.append(len(set(s[l:r])))
		return res


class Solution:

	def SolveQueris(self, str, Query):
		r = []
		for i in Query:
			r.append(self.findunique(str[i[0] - 1:i[1]]))
		return r

	def findunique(self, s):
		d = dict()
		for i in s:
			d[i] = 0
		return len(d)


class Solution:

	def SolveQueris(self, str, Query):
		l = []
		w = []
		for i in str:
			l.append(i)
		for i in Query:
			k = []
			g = []
			for j in range(i[0] - 1, i[1]):
				if l[j] not in k:
					k.append(l[j])
			w.append(len(k))
		return w


class Solution:

	def SolveQueris(self, str, Query):
		a = []
		for i in Query:
			b = str[i[0] - 1:i[1]]
			a.append(len(set(b)))
		return a


class Solution:

	def SolveQueris(self, _str, Query):
		a = []
		for _list in Query:
			substring = _str[_list[0] - 1:_list[1]]
			a.append(len(set(substring)))
		return a


from copy import copy

class Solution:

	def SolveQueris(self, str, Query):
		records = [[0] * 26 for _ in range(len(str) + 1)]
		for (i, _) in enumerate(str):
			idx = ord(str[i]) - ord('a')
			for j in range(26):
				if j != idx:
					records[i + 1][j] = records[i][j]
				else:
					records[i + 1][j] += records[i][j] + 1
		ans = []
		for (s, e) in Query:
			cnt = 0
			for i in range(26):
				if records[e][i] - records[s - 1][i] > 0:
					cnt += 1
			ans.append(cnt)
		return ans


class Solution:

	def SolveQueris(self, str, Query):
		out = []
		a = [[0 for i in range(26)] for j in range(len(str) + 1)]
		for i in range(len(str)):
			for k in range(len(a[i + 1])):
				if k == ord(str[i]) - 97:
					a[i + 1][k] = a[i][k] + 1
				else:
					a[i + 1][k] = a[i][k]
		for j in Query:
			l = j[0]
			c = 0
			r = j[1]
			if l == r:
				out.append(1)
			else:
				for (i, j) in zip(a[r], a[l - 1]):
					if i - j > 0:
						c += 1
				out.append(c)
		return out


class Solution:

	def SolveQueris(self, str, Query):
		unique_chars = [[0] * (len(str) + 1) for _ in range(26)]
		for english_ch_idx in range(26):
			ch = chr(ord('a') + english_ch_idx)
			prefix_sum = 0
			for idx in range(1, len(str) + 1):
				if str[idx - 1] == ch:
					prefix_sum += 1
				unique_chars[english_ch_idx][idx] = prefix_sum
		result = []
		for query in Query:
			uniques = 0
			for ch_idx in range(26):
				if unique_chars[ch_idx][query[1]] - unique_chars[ch_idx][query[0] - 1] != 0:
					uniques += 1
			result.append(uniques)
		return result


class Solution:

	def SolveQueris(self, s, Query):
		l = [0 for i in range(26)]
		d = dict()
		d[-1] = [0 for i in range(26)]
		l1 = []
		for i in range(len(s)):
			l[ord(s[i]) - ord('a')] += 1
			d[i] = [i for i in l]
		for i in Query:
			(a, b) = (i[0] - 2, i[1] - 1)
			(x, y) = (d[a], d[b])
			count = 0
			for j in range(len(x)):
				if y[j] - x[j] == 0:
					continue
				count = count + 1
			l1.append(count)
		return l1


class Solution:

	def SolveQueris(self, str, Query):
		l = []
		for i in range(len(Query)):
			k = Query[i][0] - 1
			k1 = Query[i][1] - 1
			s = str[k:k1 + 1]
			s1 = set(s)
			l.append(len(s1))
		return l


class Solution:

	def SolveQueris(self, s, Q):
		result = []
		for i in Q:
			new_s = s[i[0] - 1:i[1]]
			result.append(len(set(new_s)))
		return result


class Solution:

	def SolveQueris(self, str, Query):
		final = []
		for i in Query:
			chars = set()
			start = i[0] - 1
			end = i[1]
			tot = len(set(str[start:end]))
			final.append(tot)
		return final


class Solution:

	def SolveQueris(self, s, q):
		s = 'a' + s
		maps = [{} for n in range(len(s))]
		temp = {}
		ans = []
		for n in range(len(s)):
			if s[n] not in temp:
				temp[s[n]] = 0
			temp[s[n]] += 1
			maps[n] = temp.copy()
		for n in q:
			[a, b] = n
			x = maps[a - 1].copy()
			y = maps[b].copy()
			for n in x:
				y[n] -= x[n]
			res = 0
			for n in y:
				if y[n]:
					res += 1
			ans.append(res)
		return ans


class Solution:

	def SolveQueris(self, s, Q):
		n = len(s)
		dp = [[0 for i in range(26)] for k in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(26):
				dp[i][j] = dp[i - 1][j]
			dp[i][ord(s[i - 1]) - ord('a')] += 1
		k = []
		for p in range(0, len(Q)):
			a = Q[p][0]
			b = Q[p][1]
			l = [0 for i in range(26)]
			for i in range(26):
				l[i] = dp[b][i] - dp[a - 1][i]
			ans = 0
			for i in l:
				if i > 0:
					ans += 1
			k.append(ans)
		return k


class Solution:

	def SolveQueris(self, str, Query):
		dp = [[0] * 26 for i in range(len(str) + 1)]
		n = len(str)
		ans = list()
		for i in range(1, n + 1):
			for j in range(26):
				dp[i][j] = dp[i - 1][j]
			dp[i][ord(str[i - 1]) - 97] = dp[i - 1][ord(str[i - 1]) - 97] + 1
		ans = list()
		for i in Query:
			(start, end) = (i[0], i[1])
			cnt = 0
			for i in range(26):
				if dp[end][i] - dp[start - 1][i] > 0:
					cnt += 1
			ans.append(cnt)
		return ans


class Solution:

	def SolveQueris(self, str, Query):
		res = []
		for i in Query:
			cnt = 0
			s1 = str[i[0] - 1:i[1]]
			p = set(s1)
			res.append(len(p))
		return res


class Solution:

	def SolveQueris(self, str, a):
		out = []
		for i in a:
			out.append(len(set(str[i[0] - 1:i[1]])))
		return out


class Solution:

	def SolveQueris(self, st, Query):
		res = []
		for q in Query:
			start = q[0] - 1
			end = q[1] - 1
			s = st[start:end + 1]
			new_set = set(s)
			res.append(len(new_set))
		return res


class Solution:

	def SolveQueris(self, str, Query):
		result = []
		for query in Query:
			char_set = set(str[query[0] - 1:query[1]])
			result.append(len(char_set))
		return result


class Solution:

	def SolveQueris(self, str, Query):
		res = []
		l = len(str)
		dp = [[0 for c in range(l + 1)] for r in range(26)]
		for r in range(26):
			for c in range(1, l + 1):
				if ord(str[c - 1]) - ord('a') == r:
					dp[r][c] = dp[r][c - 1] + 1
				else:
					dp[r][c] = dp[r][c - 1]
		for q in Query:
			l = q[0]
			r = q[1]
			count = 0
			for row in range(26):
				if dp[row][r] - dp[row][l - 1] > 0:
					count += 1
			res.append(count)
		return res


class Solution:

	def SolveQueris(self, str, queries):
		length = []
		for query in queries:
			(left, right) = query
			length.append(len(set(str[left - 1:right])))
		return length


class Solution:

	def unique(self, str, n, b):
		d = {}
		p = [0 for i in range(n)]
		ind = b
		for i in range(b, n):
			try:
				d[str[i]] += 1
			except:
				d[str[i]] = 1
			p[ind] = len(d.keys())
			ind += 1
		return p

	def SolveQueris(self, str, Query):
		n = len(str)
		dp = [[0 for i in range(n)] for j in range(n)]
		for i in range(n):
			dp[i] = self.unique(str, n, i)
		ans = []
		for i in Query:
			ans.append(dp[i[0] - 1][i[1] - 1])
		return ans


class Solution:

	def SolveQueris(self, str, Query):
		ans = [0] * len(Query)
		d = set()
		for i in range(len(Query)):
			a = Query[i][0]
			b = Query[i][1]
			for j in range(a, b + 1):
				d.add(str[j - 1])
			ans[i] = len(d)
			d = set()
		return ans