An encoded string S consisting of alphabets(lowercase) and integers(1<=num<=9) is given, the task is to decode it and print the character at the 'K'th position in the string. The pattern in which the strings were encoded were as follows :
original string: jonjonsnowjonjonsnowjonjonsnow
encoded string: jon2snow3
Note: encoded string will always start with an alphabet and end with a number.
Example 1:
Input:
str = "jon2snow3"
k = 8
Output:
n
Explanation:
The given string after decoding it will be 
as such: jonjonsnowjonjonsnowjonjonsnow. 
8th character in the string after decoding is:'n'.
Example 2:
Input:
str = "q3"
k = 3
Output:
q
Explanation:
The given string after decoding it will be
as such: qqq. 3rd character in the string 
after decoding is:'q'.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function decodeIt() which takes the string str and an integer k as input parameters and returns the kth character of the mentioned string.
Expected Time Complexity: O(N), Where N is the size of the original string.
Expected Auxiliary Space: O(N)
Constraints:
2 <= |str| <= 35
1 <= k <= N

Difficulty: EASY
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(N), Where N is the size of the original string.
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3

class Solution:

    def decodeIt(self, Str, k):
        # code here

Solutions:
class Solution:

	def decodeIt(self, Str, k):
		decoded_string = ''
		current_position = 0
		for char in Str:
			if char.isalpha():
				decoded_string += char
				current_position += 1
			elif char.isdigit():
				repeat_count = int(char)
				decoded_string *= repeat_count
				current_position *= repeat_count
			if current_position >= k:
				return decoded_string[k - 1]
		return decoded_string[k - 1]


class Solution:

	def decodeIt(self, Str, k):
		curstr = ''
		curnum = 0
		for it in Str:
			if it.isdigit():
				curnum = int(it)
				curstr = curnum * curstr
			else:
				curstr += it
		return curstr[k - 1]


class Solution:

	def decodeIt(self, Str, k):
		s = ''
		c = ''
		for i in range(len(Str)):
			if Str[i].isnumeric():
				s = c * int(Str[i])
				c = s
			else:
				c += Str[i]
		return s[k - 1]


class Solution:

	def decodeIt(self, Str, k):
		st = ''
		for i in Str:
			if i.isalpha():
				st += i
			else:
				st *= int(i)
		return st[k - 1]


class Solution:

	def decodeIt(self, Str, k):
		b = ''
		for i in Str:
			if i >= 'a' and i <= 'z':
				b += i
			else:
				b += (int(i) - 1) * b
		return b[k - 1]


import re

class Solution:

	def decodeIt(self, Str, k):
		arr1 = re.findall('\\d+', Str)
		s = ''
		while len(arr1) > 0:
			val = arr1[0]
			ind = Str.find(val)
			sub = Str[0:ind]
			s = s + sub
			sub = s
			for i in range(0, int(val) - 1):
				s = s + sub
			arr1.pop(0)
			Str = Str[ind + len(val):]
		return s[k - 1]


class Solution:

	def decodeIt(self, strg, k):
		stack = []
		for i in strg:
			if i.isnumeric():
				news = ''
				while stack:
					news += stack.pop(0)
				news = news * int(i)
				stack.append(news)
			else:
				stack.append(i)
		news = ''
		while stack:
			news += stack.pop(0)
		return news[k - 1]


class Solution:

	def decodeIt(self, Str, k):
		st = ''
		for i in Str:
			if i.isalpha():
				st += i
			elif i.isdigit():
				st = st * int(i)
		n = st[k - 1]
		return n


class Solution:

	def decodeIt(self, Str, k):
		ans = ''
		for i in Str:
			if i >= 'a' and i <= 'z':
				ans += i
			else:
				ans *= ord(i) - ord('0')
		return ans[k - 1]


class Solution:

	def decodeIt(self, Str, k):
		str1 = ''
		res = ''
		ans = ''
		count = 0
		for i in range(len(Str)):
			if Str[i].isdigit() == 0:
				str1 += Str[i]
			else:
				count = int(Str[i])
				while count != 0:
					res += str1
					count = count - 1
				ans = res
				str1 = ''
				str1 += ans
				res = ''
		return ans[k - 1]


class Solution:

	def decodeIt(self, Str, k):
		word = ''
		number = 1
		for i in range(len(Str)):
			try:
				number = int(Str[i])
				word = word * number
			except:
				word += Str[i]
		return word[k - 1]


class Solution:

	def decodeIt(self, Str, k):
		s = ''
		for i in Str:
			if i >= '0' and i <= '9':
				s = s * int(i)
			else:
				s += i
		return s[k - 1]


class Solution:

	def decodeIt(self, Str, k):
		n = 0
		for (i, ele) in enumerate(Str):
			n = n * int(ele) if ele.isdigit() else n + 1
			if k <= n:
				break
		for j in range(i, -1, -1):
			ele = Str[j]
			if ele.isdigit():
				n /= int(ele)
				k %= n
			else:
				if k == n or k == 0:
					return ele
				n -= 1


class Solution:

	def decodeIt(self, Str, k):
		temp = ''
		word = ''
		for i in Str:
			if i >= '1' and i <= '9':
				for i in range(int(i)):
					temp += word
				word = temp
				temp = ''
			else:
				word += i
		return word[k - 1]


class Solution:

	def decodeIt(self, Str, k):
		kp = ''
		for i in range(len(Str)):
			if not Str[i].isdigit():
				kp += Str[i]
			else:
				kp = kp * int(Str[i])
		return kp[k - 1]


class Solution:

	def decodeIt(self, Str, k):
		t = ''
		for i in Str:
			if i.isdigit():
				t = t * int(i)
			else:
				t += i
		return t[k - 1]


class Solution:

	def decodeIt(self, Str, k):
		s = ''
		for i in range(len(Str)):
			if i != 0:
				if Str[i].isnumeric():
					if s == '':
						s += Str[:i] * int(Str[i])
					else:
						a = int(Str[i])
						s += s * (a - 1)
				elif s != '':
					s += Str[i]
		return s[k - 1]


class Solution:

	def decodeIt(self, Str, k):
		e = ''
		for i in Str:
			if 47 < ord(i) < 58:
				e *= int(i)
			else:
				e += i
		return e[k - 1]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		Str = input()
		k = int(input())
		solObj = Solution()
		print(solObj.decodeIt(Str, k))


class Solution:

	def decodeIt(self, s, k):
		a = ''
		for i in s:
			if i.isnumeric():
				a = a * int(i)
			else:
				a += i
			if len(a) >= k:
				return a[k - 1]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		Str = input()
		k = int(input())
		solObj = Solution()
		print(solObj.decodeIt(Str, k))


class Solution:

	def decodeIt(self, Str, k):
		s = ''
		m = Str[:len(Str) - 1]
		x = Str[-1]
		for i in m:
			if i.isdigit():
				s = s * int(i)
			else:
				s += i
		s = s * int(x)
		return s[k - 1]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		Str = input()
		k = int(input())
		solObj = Solution()
		print(solObj.decodeIt(Str, k))


class Solution:

	def decodeIt(self, Str, k):
		c = ''
		d = ''
		a = '123456789'
		for i in Str:
			if i not in a:
				c = c + i
			else:
				f = ''
				for i in range(int(i)):
					f = f + c
				c = f
		return c[k - 1]


class Solution:

	def decodeIt(self, Str, k):
		st = ''
		for c in Str:
			if c.isnumeric():
				st = st * int(c)
			else:
				st += c
		return st[k - 1]


import re

class Solution:

	def decodeIt(self, Str, k):
		res = re.split('(\\d+)', Str)
		i = 0
		word = ''
		while res[i] != '':
			word += res[i]
			word = word * int(res[i + 1])
			i += 2
		return word[k - 1]


class Solution:

	def decodeIt(self, Str, k):
		l = ''
		for i in range(len(Str)):
			if Str[i] >= '1' and Str[i] <= '9':
				l = l * int(Str[i])
			else:
				l += Str[i]
		return l[k - 1]


class Solution:

	def decodeIt(self, Str, k):
		text = Str
		words = []
		freq = []
		i = 0
		n = len(text)
		while i < n:
			tmp_word = ''
			num = ''
			while i < n and ord(text[i]) >= ord('a') and (ord(text[i]) <= ord('z')):
				tmp_word += text[i]
				i += 1
			words.append(tmp_word)
			while i < n and ord(text[i]) >= ord('0') and (ord(text[i]) <= ord('9')):
				num += text[i]
				i += 1
			num = int(num)
			freq.append(num)
		orig_text = ''
		num_words = len(words)
		i = 0
		while i < num_words:
			new_text = ''
			for j in range(freq[i]):
				new_text += orig_text + words[i]
			orig_text = new_text
			if len(orig_text) >= k:
				return orig_text[k - 1]
			i += 1
		return ''


class Solution:

	def decodeIt(self, S, k):
		res = ''
		c = 0
		i = 0
		n = len(S)
		while i < len(S):
			while i < len(S) and S[i].isdigit():
				c = c * 10 + int(S[i])
				i += 1
			if S[i - 1].isdigit():
				res = res * c
				c = 0
			if i >= n:
				break
			res += S[i]
			i += 1
		return res[k - 1]


class Solution:

	def decodeIt(self, Str, l):
		k = ''
		for i in Str:
			if i >= '1' and i <= '9':
				k += (int(i) - 1) * k
				continue
			k += i
		return k[l - 1]


class Solution:

	def decodeIt(self, Str, k):
		s = '1234567890'
		st1 = ''
		for i in Str:
			if i not in s:
				st1 = st1 + i
			else:
				st1 = st1 * int(i)
		return st1[k - 1]


class Solution:

	def decodeIt(self, Str, k):
		p = ''
		t = Str[-1]
		for i in Str[:len(Str) - 1]:
			s = ''
			if i.isalpha():
				p += i
			if i.isdigit():
				p *= int(i)
		decoded = p * int(t)
		return decoded[k - 1]


class Solution:

	def decodeIt(self, a, k):
		res = ''
		for i in a:
			if i.isalpha():
				res += i
			else:
				res *= int(i)
		return res[k - 1]


class Solution:

	def decodeIt(self, Str, k):
		newstr = ''
		for ind in range(len(Str)):
			if not Str[ind].isnumeric():
				newstr += Str[ind]
			else:
				newstr = newstr * int(Str[ind])
		return newstr[k - 1]


class Solution:

	def decodeIt(self, Str, k):
		new_string = ''
		for i in Str:
			if i.isnumeric():
				new_string = new_string * int(i)
			else:
				new_string += i
		if len(new_string) < k:
			return -1
		return new_string[k - 1]


class Solution:

	def decodeIt(self, Str, k):
		newstr = ''
		for i in Str:
			if i >= 'a' and i <= 'z':
				newstr += i
			else:
				newstr *= ord(i) - 48
		return newstr[k - 1]


class Solution:

	def decodeIt(self, Str, k):
		ans = ''
		for i in Str:
			if i.isdigit():
				s = ans
				for j in range(int(i) - 1):
					ans += s
			else:
				ans += i
		return ans[k - 1]


class Solution:

	def decodeIt(self, Str, k):
		ans = ''
		for i in Str:
			if i.isnumeric():
				s = Str[0:Str.index(i)]
				s1 = Str[0:Str.index(i) + 1]
				s = s * int(i)
				Str = Str.replace(s1, s)
		return Str[k - 1]