The jet's speed is changed after every mile covered on it's runway. It follows a specific pattern for the speed. Starting from 1 it goes like 1, 7, 16, 21, 81, 63, 256 . . .  and so on. Given N find its speed after Nth mile.
 
Example 1:
Input : N = 3
Output: 16
Explanation: Speed of jet after 3rd mile
is 16.
Example 2:
Input: N = 5
Output: 81
Explanation: Speed of jet after 5th mile 
is 81.
 
Your Task:
You don't need to read or print anyhting. Your task is to complete the function Nth_mileSpeed() which taked N as input parameter and returns jet's speed after Nth mile.
 
Expected Time Complexity: O(N)
Expected Space Complexity: O(1)
 
Constraints:
1 <= N <= 60

Source: geeksforgeeks | Difficulty: EASY

Starter code: #User function Template for python3

class Solution:
	def Nth_mileSpeed(self, n):
		# Code here

Solutions:
class Solution:

	def Nth_mileSpeed(self, n):
		if n % 2 != 0:
			return (n - n // 2) ** 4
		else:
			return 7 * 3 ** (n // 2 - 1)


class Solution:

	def Nth_mileSpeed(self, n):
		if n % 2 == 1:
			return int(((n + 1) / 2) ** 4)
		elif n % 2 == 0:
			return int(7 * 3 ** (n / 2 - 1))


class Solution:

	def Nth_mileSpeed(self, n):
		a = []
		b = []
		for i in range(0, n // 2 + 1):
			a.append((i + 1) ** 4)
		m = 0
		for i in range(1, n, 2):
			b.append(7 * 3 ** m)
			m = m + 1
		c = []
		for i in range(min(len(a), len(b))):
			c.append(a[i])
			c.append(b[i])
		c.append(a[-1])
		if n % 2 == 0:
			return c[-2]
		else:
			return c[-1]


class Solution:

	def Nth_mileSpeed(self, n):
		l = []
		l.append(1)
		l.append(7)
		i = 1
		c = 2
		while i <= 60:
			if i % 2 == 1:
				l.append(pow(c, 4))
				c += 1
			else:
				l.append(l[i - 1] * 3)
			i += 1
		return l[n - 1]


class Solution:

	def Nth_mileSpeed(self, n):
		if n % 2:
			return (n // 2 + 1) ** 4 % 2 ** 31
		return 7 * 3 ** (n // 2 - 1)


class Solution:

	def Nth_mileSpeed(self, n):
		c = [1, 7]
		k = 7
		p = 1
		for i in range(2, n):
			if i & 1:
				k = k * 3
				c.append(k)
			else:
				p += 1
				j = p ** 4
				c.append(j)
		return c[n - 1]


class Solution:

	def Nth_mileSpeed(self, n):
		a = 1
		k = 1
		s = 1
		for i in range(n):
			if i % 2 != 0:
				a = 7 * k
				k *= 3
			else:
				a = s ** 4
				s += 1
		return a


class Solution:

	def Nth_mileSpeed(self, n):
		if n % 2:
			return ((n + 1) // 2) ** 4
		a = 7
		r = 3 ** (n // 2 - 1)
		return a * r
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.Nth_mileSpeed(n)
		print(ans)


class Solution:

	def Nth_mileSpeed(self, n):
		m = (n + 1) // 2
		if n % 2 == 0:
			return int(7 * 3 ** (m - 1))
		else:
			return int(m * m * m * m)