A Fibonacci series (starting from 1) written in order without any spaces in between, thus producing a sequence of digits. Find the nth digit in the sequence.
Example 1:
Input: n = 3
Output: 2 
Explanation: 3rd digit of fibonacci 
series is 2(1123.....).
Example 2:
Input: n = 7
Output: 1
Explanation: 7th digit of fibonacci
series is 1(11235811.....).
Your Task:  
You dont need to read input or print anything. Complete the function nthFibonacciDigit() which takes n as input parameter and returns nth digit of fabonacci series. 
Expected Time Complexity: O(n*m)
Expected Auxiliary Space: O(n)
Constraints:
1<= n <=100

Difficulty: EASY
Tags: Mathematics
Expected Time Complexity: O(n*m)
Expected Auxiliary Space: O(n)

Starter code:
#User function Template for python3

class Solution:

    def nthFibonacciDigit (ob, n):

        # code here 

Solutions:
class Solution:

	def __init__(self):
		self.fl = self.fib()

	def fib(self):
		(a, b, res, n) = (1, 1, ['1', '1'], 100)
		for i in range(n - 2):
			c = a + b
			res.extend(list(str(c)))
			a = b
			b = c
		return res

	def nthFibonacciDigit(self, n):
		return self.fl[n - 1]


class Solution:

	def nthFibonacciDigit(ob, n):
		k = [1, 1, 2, 3, 5, 8, 13, 21]
		while len(k) <= n:
			k.append(k[-1] + k[-2])
		s = ''
		for i in range(len(k)):
			s = s + str(k[i])
		return s[n - 1]


class Solution:

	def nthFibonacciDigit(ob, n):
		s = '1'
		(a, b) = (0, 1)
		for i in range(n + 1):
			c = a + b
			a = b
			b = c
			s += str(c)
		return s[n - 1]


class Solution:

	def nthFibonacciDigit(ob, n):
		(f1, f2) = (1, 1)
		s = ''
		s = s + str(f1) + str(f2)
		if n == 1:
			return 1
		for i in range(2, n):
			k = f1 + f2
			s += str(k)
			f1 = f2
			f2 = k
		return s[n - 1]


class Solution:

	def nthFibonacciDigit(ob, n):
		if n < 2:
			return 1
		else:
			a = 1
			b = 1
			fib = [0] * n
			fib[0] = a
			fib[1] = b
			for i in range(2, n):
				c = a + b
				a = b
				b = c
				fib[i] = c
			new_list = []
			for i in fib:
				for d in str(i):
					new_list.append(d)
			return int(new_list[n - 1])


class Solution:

	def nthFibonacciDigit(ob, n):
		x = [1, 1]
		for i in range(n - 2):
			x.append(x[-1] + x[-2])
		y = ''
		for i in x:
			y += str(i)
		return y[n - 1]


class Solution:

	def nthFibonacciDigit(ob, n):
		fs = [0, 1]
		st = '1'
		for i in range(2, n + 2):
			fs.append(fs[i - 1] + fs[i - 2])
			st += str(fs[i - 1] + fs[i - 2])
		return st[n - 1]


class Solution:

	def nthFibonacciDigit(ob, n):
		res = '01'
		x = 2
		(a, b, c) = (0, 1, 1)
		while x <= n:
			res += str(c)
			a = b
			b = c
			c = a + b
			x = len(res)
		return res[n]


class Solution:

	def nthFibonacciDigit(ob, n):
		(s, a, b) = ('11', 1, 1)
		while len(s) < n:
			(a, b) = (b, a + b)
			s += str(b)
		return s[n - 1]


class Solution:

	def nthFibonacciDigit(ob, n):
		(s, a, b, i) = ('11', 1, 1, 2)
		while i < n:
			(a, b) = (b, a + b)
			c = str(b)
			s += c
			i += len(c)
		return s[n - 1]


class Solution:

	def nthFibonacciDigit(ob, n):
		(a, b) = (1, 1)
		c = a + b
		res = ''
		res = str(a) + str(b)
		for i in range(100):
			c = a + b
			res = res[:] + str(c)
			(a, b) = (b, c)
		return int(res[n - 1])


class Solution:

	def nthFibonacciDigit(ob, n):
		(a, b) = (1, 1)
		l = [1, 1]
		for i in range(2, n):
			r = a + b
			l.append(r)
			a = b
			b = r
		s = ''
		for i in l:
			s += str(i)
		return s[n - 1]


class Solution:

	def nthFibonacciDigit(ob, n):
		if n == 1:
			return 1
		a = 1
		b = 0
		p = '1'
		for i in range(2, n + 1):
			c = a
			a = a + b
			b = c
			x = str(a)
			p = p + x
		return p[n - 1]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.nthFibonacciDigit(n))


class Solution:

	def nthFibonacciDigit(ob, n):
		res = '11'
		a1 = 1
		a2 = 1
		while len(res) < n:
			temp = a2
			a2 = a1 + a2
			a1 = temp
			res += str(a2)
		return res[n - 1]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.nthFibonacciDigit(n))


class Solution:

	def nthFibonacciDigit(ob, n):

		def nthFibonacci(n):
			f = [0] * (n + 1)
			x = 1000000007
			f[0] = 0
			f[1] = 1
			for i in range(2, n + 1):
				f[i] = f[i - 1] + f[i - 2]
			return f[n]
		if n < 1:
			return 0
		digit = None
		count = 0
		digits = []
		num = 1
		while num <= n:
			nf = nthFibonacci(num)
			temp = []
			while nf > 0:
				digit = nf % 10
				nf = int(nf / 10)
				count += 1
				temp.append(digit)
			num += 1
			temp.reverse()
			digits += temp
			if count > n:
				break
		return digits[n - 1]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.nthFibonacciDigit(n))


class Solution:

	def nthFibonacciDigit(ob, n):
		t = '11'
		l = [1, 1]
		while len(t) < n:
			d = l[-1] + l[-2]
			t += str(d)
			l.append(d)
		return t[n - 1]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.nthFibonacciDigit(n))


class Solution:

	def nthFibonacciDigit(ob, n):
		nums = ''
		(a, b) = (0, 1)
		while 1:
			(a, b) = (b, a + b)
			nums += str(a)
			if len(nums) >= n:
				return nums[n - 1]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.nthFibonacciDigit(n))


class Solution:

	def nthFibonacciDigit(ob, n):
		l = []
		s = '11'
		a = 1
		b = 1
		for i in range(n):
			term = a + b
			s += str(term)
			a = b
			b = term
		return s[n - 1]


class Solution:

	def nthFibonacciDigit(ob, n):

		def nthFibonacci(n):
			f = [0] * (n + 1)
			x = 1000000007
			f[0] = 0
			f[1] = 1
			for i in range(2, n + 1):
				f[i] = f[i - 1] + f[i - 2]
			return f[n]
		if n < 1:
			return 0
		digit = None
		count = 0
		digits = []
		num = 1
		while num <= n:
			nf = nthFibonacci(num)
			temp = []
			while nf > 0:
				digit = nf % 10
				nf = int(nf / 10)
				count += 1
				temp.append(digit)
			num += 1
			temp.reverse()
			digits += temp
			if count > n:
				break
		return digits[n - 1]


class Solution:

	def nthFibonacciDigit(self, n):
		str1 = ''
		a = 1
		b = 0
		while len(str1) <= n:
			ans = a + b
			a = b
			b = ans
			str1 = str1 + str(ans)
		if len(str1) > n:
			return str1[n - 1]


class Solution:

	def nthFibonacciDigit(ob, n):
		st = '1'
		a = 0
		b = 1
		while len(st) <= n:
			c = a + b
			a = b
			b = c
			st = st + str(c)
		return st[n - 1]


class Solution:

	def nthFibonacciDigit(ob, n):
		x = [0, 1]
		for i in range(2, 101):
			x.append(x[i - 1] + x[i - 2])
		x.pop(0)
		s = ''
		for i in x:
			s += str(i)
		return s[n - 1]


class Solution:

	def nthFibonacciDigit(self, n):
		a = 1
		b = 1
		p = 0
		s = str(a) + str(b)
		while p - 2 < n and len(s) < n:
			c = a + b
			s = s + str(c)
			a = b
			b = c
			p = p + 1
		return s[n - 1]


class Solution:

	def nthFibonacciDigit(ob, n):
		a = 0
		b = 0
		c = 1
		i = 0
		s = ''
		while i <= n:
			s += str(c)
			a = b
			b = c
			c = a + b
			i = i + 1
		return s[n - 1]


class Solution:

	def nthFibonacciDigit(ob, n):
		x = 0
		y = 1
		i = 0
		sting = '1'
		while len(sting) <= n:
			temp = x + y
			x = y
			y = temp
			sting += str(temp)
		return sting[n - 1]


class Solution:

	def nthFibonacciDigit(ob, n):
		prev_num = 0
		current_num = 1
		fibo = '1'
		for i in range(1, n):
			preprev = prev_num
			prev_num = current_num
			current_num = prev_num + preprev
			fibo = fibo + str(current_num)
		return fibo[n - 1]


class Solution:

	def nthFibonacciDigit(ob, n):
		f = ['1', '1']
		for i in range(2, n + 2):
			f.append(str(int(f[i - 1]) + int(f[i - 2])))
		f = ''.join(f)
		return f[n - 1]


class Solution:

	def nthFibonacciDigit(ob, n):
		fib = [1, 1]
		st = '11'
		for i in range(n):
			k = fib[i] + fib[i + 1]
			fib.append(k)
			st += str(k)
		return st[n - 1]


class Solution:

	def nthFibonacciDigit(ob, n):
		t1 = 1
		t2 = 1
		i = 2
		l = str(t1) + str(t2)
		if len(l) >= n:
			return l[n - 1]
		while i <= n:
			if len(l) >= n:
				return l[n - 1]
			t3 = t1 + t2
			t1 = t2
			t2 = t3
			l += str(t3)
			i += 1


class Solution:

	def nthFibonacciDigit(ob, n):
		fibb = '1'
		a = 0
		b = 1
		temp = a + b
		fibb += str(temp)
		a = True
		nth = len(fibb) - 1
		if n <= 0:
			return 0
		elif n == 1:
			return 1
		elif n == 2:
			return 1
		else:
			while a:
				nth += 1
				a = b
				b = temp
				temp = a + b
				fibb += str(temp)
				if nth == n:
					return fibb[n - 1]
					break


class Solution:

	def nthFibonacciDigit(ob, n):
		f1 = 0
		f2 = 1
		l = []
		s = ''
		for i in range(30):
			l.append(f2)
			next = f1 + f2
			f1 = f2
			f2 = next
			s = ''.join((str(i) for i in l))
		return int(s[n - 1])


class Solution:

	def nthFibonacciDigit(ob, n):
		fabi = []
		a = 1
		b = 1
		fabi.append(a)
		fabi.append(b)
		c = 0
		while len(fabi) <= n:
			c = a + b
			fabi.append(c)
			a = b
			b = c
		ans = ''.join((str(ele) for ele in fabi))
		return ans[n - 1]


class Solution:

	def nthFibonacciDigit(ob, n):
		strr = ''
		if n == 1:
			strr = '1'
		elif n == 2:
			strr = '11'
		else:
			strr = '11'
			i = 3
			a = 1
			b = 1
			c = a + b
			while i <= n + 1:
				strr += str(c)
				(a, b) = (b, c)
				c = a + b
				i += 1
		return strr[n - 1]


class Solution:

	def nthFibonacciDigit(ob, n):
		sum = 0
		i = 1
		j = 0
		string = '11'
		k = 0
		while k <= 101:
			sum = i + j
			string = string + str(sum)
			j = i
			i = sum
			k = k + 1
		ch = string[n]
		return ch


class Solution:

	def nthFibonacciDigit(ob, n):
		lst = [1, 1]
		for i in range(2, n):
			lst.append(lst[i - 1] + lst[i - 2])
		string = ''.join(map(str, lst))
		return string[n - 1]


class Solution:

	def nthFibonacciDigit(ob, n):
		sum = 0
		a = 0
		b = 1
		s = ''
		s = s + str(b)
		for i in range(0, n):
			sum = a + b
			a = b
			b = sum
			s = s + str(sum)
		l = []
		for i in s:
			l.append(i)
		return l[n - 1]