Given a number N. Find the last two digits of the Nth fibonacci number.
Note: If the last two digits are 02, return 2.
Example 1:
Input:
N = 13
Output:
33
Explanation:
The 13th Fibonacci number is 233.
So last two digits are 3 and 3.
Example 2:
Input:
N = 255
Output:
70
Explanation:
The 255th fibonacci number is  875715953430-
18854458033386304178158174356588264390370.
Thus, last two digits are 7 and 0.
Your Task:
You don't need to read input or print anything.Your task is to complete the function fibonacciDigits() which takes a number N as input parameter and returns the last two digits of the Nth fibonacci number.
Expected Time Complexity:O(K)
Expected Auxillary Space:O(K)
K is of the order 10^{2}.
Constraints:
1<=N<=10^{18}

Difficulty: EASY
Tags: Mathematics
Expected Time Complexity: O(K)
Expected Auxiliary Space: O(K)

Starter code:
#User function Template for python3

class Solution:
    def fibonacciDigits(self,N):
        #code here

Solutions:
class Solution:

	def fibonacciDigits(self, N):
		return int(str(self.gfn(N % 300))[-2:])

	def gfn(self, n):
		if n < 1:
			return 0
		n1 = 0
		n2 = 1
		while n > 1:
			n2 += n1
			n1 = n2 - n1
			n -= 1
		return n2


class Solution:

	def fibonacciDigits(self, N):
		n1 = 0
		n2 = 1
		k = 1
		while N > 300:
			N = N % 300
		while k <= N:
			k += 1
			(n1, n2) = ((n1 + n2) % 100, n1 % 100)
		return int(n1 % 100)


class Solution:

	def fibonacciDigits(self, N):
		(a, b) = (0, 1)
		k = 1
		while N > 300:
			N = N % 300
		while k <= N:
			k += 1
			(a, b) = ((a + b) % 100, a % 100)
		return int(a % 100)


class Solution:

	def fibonacciDigits(self, N):
		(a, b, c, N) = (1, 1, 2, N % 300)
		if N == 0:
			return 0
		if N == 1 or N == 2:
			return 1
		while c < N:
			(a, b) = (b, (a + b) % 100)
			c += 1
			if c == N:
				return b


class Solution:

	def fibonacciDigits(self, N):
		fib = [0] * 300
		fib[0] = 0
		fib[1] = 1
		fib[2] = 1
		for i in range(3, len(fib)):
			fib[i] = (fib[i - 2] + fib[i - 1]) % 100
		return fib[N % 300]


class Solution:

	def fibonacciDigits(self, N):
		fibonacci = []
		fibonacci.append(0)
		fibonacci.append(1)
		for i in range(2, 300):
			fibonacci.append((fibonacci[i - 1] + fibonacci[i - 2]) % 100)
		return fibonacci[N % 300]


class Solution:

	def fibonacciDigits(self, n):
		n = n % 300
		if n in {0, 1}:
			return n
		a = 0
		b = 1
		c = 0
		for i in range(2, n + 1):
			c = (a + b) % 100
			a = b % 100
			b = c % 100
		return c % 300


class Solution:

	def fibonacciDigits(self, N):
		x = 1
		y = 1
		c = 2
		ans = [0, 1, 1]
		while c < 301:
			(x, y) = (y, y + x)
			c += 1
			ans.append(y % 100)
		return ans[N % 300]


class Solution:

	def fibonacciDigits(self, N):
		m = N % 300
		a = 0
		b = 1
		if m == 0 or m == 1:
			return m
		for i in range(1, m):
			sum = (a + b) % 100
			(a, b) = (b % 100, sum)
		return sum % 100


class Solution:

	def fibonacciDigits(self, N):
		dp = [i for i in range(300)]
		dp[0] = 0
		dp[1] = 1
		dp[2] = 1
		for i in range(3, 300):
			dp[i] = (dp[i - 1] + dp[i - 2]) % 100
		return dp[int(N % 300)]


class Solution:

	def fast_fibonacci(self, ans, n):
		if n == 0:
			ans[0] = 0
			ans[1] = 1
			return
		self.fast_fibonacci(ans, n // 2)
		a = ans[0]
		b = ans[1]
		c = 2 * b - a
		c = a * c
		d = a * a + b * b
		if n % 2 == 0:
			ans[0] = c
			ans[1] = d
		else:
			ans[0] = d
			ans[1] = c + d

	def fibonacciDigits(self, N):
		ans = [0, 0]
		self.fast_fibonacci(ans, N % 300)
		return ans[0] % 100


class Solution:

	def fibonacciDigits(self, N):
		a = 1
		b = 1
		c = 0
		N = N % 300
		if N == 1:
			return a
		if N == 2:
			return b
		for i in range(3, N + 1):
			c = int(a + b) % 100
			a = b % 100
			b = c % 100
		return c


class Solution:

	def fibonacciDigits(self, N):
		fib = [0] * 300
		fib[0] = 0
		fib[1] = 1
		for i in range(2, min(299, N) + 1):
			fib[i] = (fib[i - 1] + fib[i - 2]) % 100
		return fib[N % 300]


class Solution:

	def fibonacciDigits(self, N):
		l = [0] * 300
		l[0] = 0
		l[1] = 1
		for i in range(2, min(N, 299) + 1):
			l[i] = (l[i - 2] + l[i - 1]) % 100
		return l[N % 300]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		ans = ob.fibonacciDigits(N)
		if ans // 10 > 0:
			print(ans)
		else:
			print(0, end='')
			print(ans)


class Solution:

	def fibonacciDigits(self, n):
		if n == 0:
			return 0
		elif n == 1:
			return 1
		else:
			a = 0
			b = 1
			for i in range(n % 900):
				c = a + b
				a = b
				b = c
			if a < 9:
				return a
			else:
				return a % 100


class Solution:

	def fibonacciDigits(self, N):
		arr = [None] * 300
		arr[0] = 0
		arr[1] = 1
		arr[2] = 1
		for i in range(3, 300):
			arr[i] = (arr[i - 2] + arr[i - 1]) % 100
		return arr[N % 300]


class Solution:

	def fibonacciDigits(self, N):
		if N == 0 or N == 1:
			return N
		f = []
		f.append(0)
		f.append(1)
		for i in range(2, 300):
			f.append((f[i - 1] + f[i - 2]) % 100)
		return f[N % 300]


import math

class Solution:

	def fibonacciDigits(self, N):
		fib = [0] * 300
		fib[0] = 0
		fib[1] = 1
		fib[2] = 1
		for i in range(3, 300):
			fib[i] = (fib[i - 1] + fib[i - 2]) % 100
		return fib[abs(N % 300)]


class Solution:

	def fibonacciDigits(self, N):
		l = list()
		l.append(0)
		l.append(1)
		l.append(1)
		s1 = 1
		s2 = 1
		s = 0
		n = 1
		while n < 300:
			s = s1 + s2
			l.append(s % 100)
			s2 = s1
			s1 = s
			n += 1
		return l[N % 300]


class Solution:

	def fibonacciDigits(self, N):
		N = N % 300
		ans = 0
		if N == 1:
			ans = 1
		elif N == 2:
			ans = 1
		a = 1
		b = 1
		for i in range(3, N + 1):
			ans = a + b
			a = b
			b = ans
		return ans % 100


class Solution:

	def fibonacciDigits(self, n):
		f = []
		f.append(0)
		f.append(1)
		for i in range(2, 300):
			f.append((f[i - 1] + f[i - 2]) % 100)
		return f[n % 300]


class Solution:

	def fib(self, n):
		if n == 0:
			return 0
		a = b = 1
		for _ in range(n - 2):
			(a, b) = (b, a + b)
		return b

	def fibonacciDigits(self, N):
		val = self.fib(N % 300)
		return int(str(val)[-2:])


class Solution:

	def fibonacciDigits(self, N):
		rem = N % 300
		a = 1
		b = 1
		if rem == 0:
			return 0
		elif rem <= 2:
			return 1
		res = 0
		temp = 0
		for i in range(3, rem + 1):
			res = a + b
			temp = res % 100
			a = b
			b = res
		return temp


class Solution:

	def fibonacciDigits(self, N):
		f = [0] * 300
		f[1] = f[2] = 1
		c = 3
		while c < 300:
			f[c] = (f[c - 1] + f[c - 2]) % 100
			c += 1
		return f[N % 300]


class Solution:

	def fibonacciDigits(self, N):
		fab = []
		tmp0 = 0
		tmp1 = 1
		tmp = 0
		mod_N = N % 300
		for i in range(1, mod_N + 1):
			tmp = tmp0 + tmp1
			fab.append(tmp)
			tmp0 = tmp1
			tmp1 = tmp
		dig = str(tmp0)
		if len(dig) < 2:
			return int(dig[0])
		if int(dig[-2]) == 0:
			return int(dig[-1])
		else:
			return int(dig[-2:])


class Solution:

	def fibonacciDigits(self, N):
		n = N % 300
		if n == 0:
			return 0
		elif n == 1:
			return 1
		out = self.matrixmul(n - 1)
		return out[0][0] % 100

	def matrixmul(self, N):
		temp = [[0, 0], [0, 0]]
		if N == 1:
			return [[1, 1], [1, 0]]
		temp = self.matrixmul(N // 2)
		lst = []
		lst.append(temp[0][0] * temp[0][0] + temp[0][1] * temp[1][0])
		lst.append(temp[0][0] * temp[0][1] + temp[0][1] * temp[1][1])
		lst.append(temp[1][0] * temp[0][0] + temp[1][1] * temp[1][0])
		lst.append(temp[1][0] * temp[0][1] + temp[1][1] * temp[1][1])
		temp[0][0] = lst[0]
		temp[0][1] = lst[1]
		temp[1][0] = lst[2]
		temp[1][1] = lst[3]
		if N % 2 == 0:
			return temp
		else:
			lst = []
			lst.append(temp[0][0] + temp[0][1])
			lst.append(temp[0][0])
			lst.append(temp[1][0] + temp[1][1])
			lst.append(temp[1][0])
			temp[0][0] = lst[0]
			temp[0][1] = lst[1]
			temp[1][0] = lst[2]
			temp[1][1] = lst[3]
			return temp


class Solution:

	def fibonacciDigits(self, N):
		l = [0, 1]
		for i in range(1, 300):
			l.append(l[i - 1] + l[i])
		if N % 300 == N:
			return l[N] % 100
		else:
			return l[N % 300] % 100


class Solution:

	def fibonacciDigits(self, N):
		if N > 300:
			N = N % 300
			if N == 0:
				return 0
			elif N == 1:
				return 1
			else:
				fib = [0] * (N + 1)
				fib[0] = 0
				fib[1] = 1
				for i in range(2, N + 1):
					fib[i] = fib[i - 2] + fib[i - 1]
					m = fib[N]
				return m % 100
		else:
			fib = [0] * (N + 1)
			fib[0] = 0
			fib[1] = 1
			for i in range(2, N + 1):
				fib[i] = fib[i - 2] + fib[i - 1]
				m = fib[N]
			return m % 100


class Solution:
	vl_all = [0, 1]
	vl = [0, 1]
	for i in range(2, 300):
		vl = [vl[1], sum(vl) % 100]
		vl_all.append(vl[1])

	def fibonacciDigits(self, N):
		return Solution.vl_all[N % 300]