Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:


Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2:


Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Graph traversal

Mathematics
Skill types: Dynamic programming

Starter code:
class Solution:
    def numSquares(self, n: int) -> int:
        

Solutions:
class Solution:

	def numSquares(self, n):
		while n % 4 == 0:
			n = n / 4
		if n % 8 == 7:
			return 4
		a = int(0)
		while a * a <= n:
			b = int(math.sqrt(n - a * a))
			if a * a + b * b == n:
				print('a=', a, 'b+', b)
				return (not not a) + (not not b)
			a += 1
		return 3


class Solution:

	def numSquares(self, n):
		import math

		def is_square(m):
			sqrt_m = int(math.sqrt(m))
			return sqrt_m * sqrt_m == m
		if is_square(n):
			return 1
		while n & 3 == 0:
			n >>= 2
		if n & 7 == 7:
			return 4
		sqrt_n = int(math.sqrt(n))
		for i in range(1, sqrt_n + 1):
			if is_square(n - i * i):
				return 2
		return 3


class Solution:

	def numSquares(self, n):

		def is_square(n):
			return int(n ** 0.5) * int(n ** 0.5) == n
		if is_square(n):
			return 1
		for i in range(1, int(n ** 0.5 + 1)):
			if is_square(n - i * i):
				return 2
		while n & 3 == 0:
			n >>= 2
		if n & 7 == 7:
			return 4
		return 3


class Solution:

	def numSquares(self, n):
		while n % 4 == 0:
			n //= 4
		if n % 8 == 7:
			return 4
		for i in range(n + 1):
			tmp = i * i
			if tmp <= n:
				if int((n - tmp) ** 0.5) ** 2 + tmp == n:
					return 1 + (0 if tmp == 0 else 1)
			else:
				break
		return 3


class Solution:

	def numSquares(self, n):
		import math
		while n % 4 == 0:
			n = n / 4
		if n % 8 == 7:
			return 4
		if round(math.sqrt(n)) ** 2 == n:
			return 1
		for i in range(1, math.ceil(math.sqrt(n))):
			res = n - i ** 2
			print(('i:,res:,', i, res))
			if round(math.sqrt(res)) ** 2 == res:
				return 2
		return 3


class Solution:

	@staticmethod
	def as_a_perfect_square(n):
		return (n ** 0.5).is_integer()

	@staticmethod
	def min_perfect_square(i, array):
		res = 1000
		for x in range(0, i // 2 + 1):
			a = array[x]
			if a >= res:
				continue
			b = array[i - 1 - x]
			if a + b < res:
				res = a + b
			if res == 2:
				return res
		return res

	def numSquares(self, n):
		array = [1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3, 2, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 3, 1, 2, 3, 4, 2, 3, 4, 2, 3, 2, 3, 1, 2, 3, 4, 2, 2, 3, 3, 3, 2, 3, 4, 3, 1, 2, 3, 2, 2, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 1, 2, 3, 3, 2, 3, 3, 4, 2, 2, 2, 3, 3, 3, 3, 4, 2, 1, 2, 3, 3, 2, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 3, 2, 2, 3, 1, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 4, 2, 3, 3, 2, 2, 3, 4, 3, 1, 2, 3, 4, 2, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 1, 2, 2, 3, 2, 2, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 2, 3, 2, 3, 2, 3, 3, 4, 3, 1, 2, 3, 3, 2, 3, 4, 3, 3, 2, 3, 2, 2, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 3, 2, 2, 3, 1, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 2, 3, 3, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 3, 1, 2, 3, 3, 2, 3, 4, 2, 2, 2, 3, 3, 3, 3, 4, 4, 2, 2, 3, 2, 2, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 1, 2, 3, 3, 2, 2, 3, 4, 3, 2, 3, 3, 3, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 2, 1, 2, 3, 2, 2, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 3, 2, 2, 3, 4, 2, 3, 4, 2, 3, 3, 3, 1, 2, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 3, 2, 2, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 3, 2, 3, 3, 2, 3, 3, 4, 2, 1, 2, 3, 3, 2, 3, 4, 4, 2, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 3, 3, 2, 3, 2, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 1, 2, 3, 3, 2, 2, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 3, 2, 3, 3, 2, 3, 3, 4, 3, 1, 2, 3, 4, 2, 3, 4, 4, 2, 2, 3, 2, 3, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 2, 3, 2, 3, 2, 3, 3, 4, 3, 3, 3, 3, 4, 2, 3, 4, 3, 2, 2, 3, 1, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 4, 3, 3, 3, 2, 3, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 2, 2, 2, 3, 3, 3, 3, 4, 3, 1, 2, 3, 3, 2, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 2, 2, 3, 3, 2, 2, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 2, 2, 3, 3, 3, 3, 4, 2, 2, 3, 3, 2, 3, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 3, 3, 2, 3, 2, 2, 3, 4, 3, 2, 3, 3, 3, 3, 3, 4, 4, 1, 2, 3, 2, 2, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 2, 2, 3, 3, 3, 2, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 3, 2, 2, 3, 1, 2, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 3, 2, 3, 3, 2, 3, 3, 4, 3, 2, 2, 3, 4, 2, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 2, 3, 2, 3, 2, 2, 3, 4, 3, 1, 2, 3, 4, 2, 3, 4, 3, 3, 2, 3, 2, 3, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 4, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 3, 2, 3, 3, 2, 2, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 1, 2, 3, 3, 2, 3, 3, 4, 3, 2, 2, 3, 4, 2, 3, 4, 2, 2, 2, 3, 3, 3, 3, 4, 2, 2, 2, 3, 3, 3, 3, 4, 3, 3, 2, 3, 2, 2, 3, 4, 3, 3, 3, 3, 4, 2, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 3, 1, 2, 3, 3, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 2, 2, 3, 3, 3, 2, 3, 4, 4, 2, 2, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 3, 3, 2, 3, 1, 2, 3, 4, 2, 2, 3, 3, 3, 2, 3, 4, 3, 3, 2, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 2, 2, 3, 3, 2, 3, 3, 4, 2, 2, 3, 3, 3, 2, 3, 4, 3, 3, 3, 3, 3, 2, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 4, 1, 2, 3, 2, 2, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 2, 2, 3, 3, 2, 2, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 3, 3, 3, 3, 3, 2, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 4, 2, 2, 3, 3, 2, 3, 4, 3, 2, 2, 3, 4, 2, 3, 4, 1, 2, 3, 3, 2, 3, 3, 4, 3, 2, 3, 3, 3, 2, 3, 4, 2, 3, 2, 3, 2, 3, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 3, 3, 2, 3, 2, 2, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 2, 1, 2, 3, 3, 2, 3, 4, 2, 2, 2, 3, 3, 3, 3, 4, 3, 2, 3, 3, 2, 2, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 3, 3, 3, 3, 2, 2, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 4, 3, 2, 3, 3, 3, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 2, 2, 2, 3, 1, 2, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 2, 3, 2, 3, 2, 3, 3, 4, 3, 3, 3, 3, 4, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 3, 2, 3, 3, 2, 3, 3, 4, 2, 1, 2, 3, 3, 2, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 3, 2, 2, 3, 2, 3, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 4, 3, 3, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 3, 3, 3, 4, 1, 2, 3, 3, 2, 2, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 2, 2, 2, 3, 3, 3, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 3, 3, 3, 3, 2, 3, 3, 4, 3, 3, 3, 3, 4, 2, 3, 4, 3, 2, 2, 3, 2, 3, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 3, 1, 2, 3, 4, 2, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 4, 3, 2, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 3, 2, 3, 3, 2, 2, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 2, 3, 3, 3, 1, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 3, 3, 2, 3, 2, 3, 3, 4, 3, 2, 2, 3, 4, 2, 3, 4, 4, 3, 3, 3, 2, 3, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 3, 2, 2, 3, 2, 2, 3, 4, 3, 3, 3, 3, 4, 3, 3, 4, 3, 3, 3, 3, 2, 3, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 4, 1, 2, 3, 3, 2, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 2, 2, 3, 3, 2, 2, 3, 4, 3, 3, 3, 3, 4, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 3, 2, 2, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 3, 2, 3, 3, 3, 2, 3, 4, 2, 3, 2, 3, 2, 2, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 3, 3, 3, 3, 2, 2, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 4, 2, 3, 3, 3, 3, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 2, 2, 2, 3, 3, 2, 3, 4, 3, 3, 3, 3, 3, 3, 3, 4, 3, 1, 2, 3, 2, 2, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 2, 2, 3, 3, 2, 3, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 3, 3, 2, 3, 2, 2, 3, 4, 3, 2, 3, 3, 3, 2, 3, 4, 2, 2, 2, 3, 3, 3, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 3, 3, 2, 3, 1, 2, 3, 4, 2, 2, 3, 3, 3, 2, 3, 4, 4, 2, 3, 3, 2, 2, 3, 4, 3, 3, 3, 3, 4, 2, 3, 4, 4, 3, 3, 3, 2, 3, 3, 4, 2, 2, 2, 3, 3, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 3, 2, 3, 3, 2, 3, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 3, 3, 3, 3, 2, 2, 3, 4, 3, 1, 2, 3, 4, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 2, 2, 2, 3, 3, 2, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 3, 2, 3, 3, 3, 3, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 4, 3, 2, 3, 2, 3, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 3, 2, 2, 3, 2, 3, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 1, 2, 3, 3, 2, 3, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 2, 2, 2, 3, 3, 3, 3, 4, 3, 3, 2, 3, 2, 2, 3, 4, 3, 3, 3, 3, 4, 3, 3, 4, 4, 2, 3, 3, 3, 2, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 3, 2, 2, 3, 2, 3, 3, 4, 3, 1, 2, 3, 3, 2, 3, 4, 4, 3, 2, 3, 2, 3, 3, 4, 3, 2, 2, 3, 4, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 2, 2, 3, 3, 3, 2, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 2, 2, 3, 3, 2, 3, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 3, 2, 3, 3, 1, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 2, 3, 3, 4, 3, 2, 2, 3, 4, 2, 3, 4, 3, 3, 2, 3, 3, 3, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 4, 2, 3, 3, 2, 2, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 2, 3, 2, 3, 2, 3, 3, 4, 3, 3, 2, 3, 3, 3, 3, 4, 2, 3, 2, 3, 2, 2, 3, 4, 3, 3, 3, 3, 4, 2, 3, 4, 3, 1, 2, 3, 3, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 3, 3, 3, 3, 3, 2, 3, 4, 2, 2, 2, 3, 3, 3, 3, 4, 3, 2, 2, 3, 2, 3, 3, 4, 3, 3, 3, 3, 4, 2, 3, 4, 3, 2, 3, 3, 2, 3, 3, 4, 3, 2, 3, 3, 3, 2, 3, 4, 4, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 1, 2, 2, 3, 2, 2, 3, 4, 2, 2, 2, 3, 3, 3, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 3, 2, 2, 3, 4, 2, 3, 4, 2, 3, 3, 3, 2, 2, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 3, 2, 3, 3, 3, 2, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 2, 3, 3, 3, 2, 3, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 2, 2, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 3, 1, 2, 3, 2, 2, 3, 4, 3, 3, 2, 3, 3, 3, 3, 4, 4, 2, 3, 3, 2, 2, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 2, 3, 2, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 3, 2, 2, 3, 2, 3, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 3, 3, 2, 3, 3, 3, 3, 4, 3, 3, 3, 3, 4, 2, 3, 4, 4, 3, 2, 3, 1, 2, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 2, 3, 3, 3, 2, 3, 3, 4, 3, 2, 2, 3, 4, 2, 3, 4, 3, 2, 3, 3, 3, 2, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 4, 2, 3, 3, 2, 2, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 2, 2, 3, 3, 2, 3, 3, 4, 3, 3, 2, 3, 3, 3, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 3, 3, 3, 3, 4, 3, 3, 4, 2, 2, 2, 3, 3, 2, 3, 4, 2, 1, 2, 3, 3, 2, 3, 4, 3, 2, 2, 3, 2, 3, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 2, 3, 2, 3, 2, 3, 3, 4, 3, 2, 3, 3, 3, 2, 3, 4, 3, 3, 2, 3, 2, 2, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 3, 2, 3, 3, 3, 3, 3, 4, 2, 2, 3, 3, 3, 2, 3, 4, 4, 3, 3, 3, 3, 2, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 3, 2, 2, 3, 2, 2, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 1, 2, 3, 3, 2, 3, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 3, 3, 3, 4, 3, 3, 2, 3, 2, 2, 3, 4, 3, 2, 2, 3, 4, 2, 3, 4, 3, 2, 2, 3, 2, 3, 3, 4, 3, 3, 2, 3, 3, 3, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 3, 2, 3, 3, 2, 2, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 4, 2, 3, 3, 2, 3, 3, 4, 3, 1, 2, 3, 4, 2, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 2, 2, 2, 3, 3, 3, 3, 4, 3, 2, 2, 3, 2, 2, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 3, 3, 2, 3, 3, 3, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 2, 2, 3, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 3, 3, 3, 3, 1, 2, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 4, 2, 2, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 3, 3, 3, 3, 3, 3, 3, 4, 2, 2, 3, 3, 3, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 3, 2, 2, 3, 2, 3, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 3, 2, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 4, 3, 3, 3, 3, 3, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 3, 1, 2, 3, 2, 2, 3, 4, 3, 2, 2, 3, 4, 2, 3, 4, 3, 2, 2, 3, 2, 3, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 4, 3, 3, 3, 2, 2, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 3, 3, 2, 3, 2, 2, 3, 4, 3, 3, 3, 3, 3, 2, 3, 4, 2, 2, 3, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 3, 2, 3, 3, 3, 2, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 1, 2, 3, 3, 2, 2, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 3, 2, 2, 3, 2, 3, 3, 4, 2, 2, 3, 3, 3, 2, 3, 4, 4, 2, 3, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 2, 3, 2, 3, 2, 2, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 2, 2, 3, 3, 2, 3, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 3, 1, 2, 3, 3, 2, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 3, 2, 3, 3, 3, 3, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 2, 2, 3, 3, 2, 2, 3, 4, 3, 3, 3, 3, 4, 2, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 3, 3, 3, 4, 4, 2, 2, 3, 2, 3, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 2, 2, 2, 3, 2, 3, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 3, 3, 3, 3, 3, 2, 3, 4, 3, 3, 3, 3, 4, 2, 3, 4, 3, 2, 2, 3, 1, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 3, 3, 3, 3, 2, 3, 3, 4, 3, 2, 2, 3, 4, 2, 3, 4, 2, 2, 2, 3, 3, 3, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 3, 3, 3, 3, 2, 2, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 3, 2, 3, 3, 2, 3, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 4, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 3, 2, 3, 3, 2, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 3, 3, 2, 3, 3, 3, 3, 4, 3, 1, 2, 3, 4, 2, 3, 4, 2, 3, 2, 3, 2, 3, 3, 4, 3, 2, 3, 3, 3, 2, 3, 4, 3, 2, 2, 3, 2, 2, 3, 4, 3, 3, 3, 3, 4, 2, 3, 4, 4, 3, 3, 3, 2, 3, 3, 4, 2, 2, 2, 3, 3, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 4, 3, 3, 3, 3, 2, 3, 4, 3, 2, 2, 3, 4, 2, 3, 4, 3, 3, 3, 3, 3, 2, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 3, 2, 2, 3, 4, 2, 3, 4, 2, 2, 3, 3, 2, 3, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 3, 3, 3, 3, 2, 2, 3, 4, 3, 3, 3, 3, 4, 2, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 3, 2, 3, 3, 3, 3, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 4, 2, 2, 3, 2, 2, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 2, 3, 3, 3, 2, 3, 3, 4, 3, 1, 2, 3, 3, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 2, 3, 2, 3, 2, 3, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 2, 3, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 3, 3, 2, 3, 3, 3, 3, 4, 3, 2, 3, 3, 3, 2, 3, 4, 3, 2, 3, 3, 2, 2, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 3, 2, 3, 3, 2, 3, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 4, 2, 2, 3, 3, 3, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 4, 3, 2, 3, 1, 2, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 2, 3, 3, 3, 2, 3, 3, 4, 3, 2, 2, 3, 4, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 2, 3, 3, 3, 2, 3, 3, 4, 3, 3, 3, 3, 3, 2, 3, 4, 2, 3, 2, 3, 2, 2, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 3, 3, 3, 3, 2, 3, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 4, 3, 3, 3, 3, 3, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 3, 1, 2, 3, 3, 2, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 3, 2, 2, 3, 2, 2, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 2, 2, 3, 3, 3, 2, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 3, 3, 3, 3, 4, 3, 3, 4, 4, 2, 2, 3, 2, 3, 3, 4, 2, 2, 3, 3, 3, 2, 3, 4, 3, 2, 2, 3, 2, 3, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 3, 3, 3, 3, 2, 2, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 4, 3, 2, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 1, 2, 3, 3, 2, 3, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 2, 2, 2, 3, 3, 3, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 3, 2, 3, 3, 2, 2, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 2, 2, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 2, 2, 2, 3, 3, 2, 3, 4, 3, 3, 3, 3, 4, 3, 3, 4, 3, 3, 2, 3, 2, 3, 3, 4, 3, 2, 3, 3, 3, 2, 3, 4, 4, 3, 2, 3, 2, 3, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 3, 1, 2, 3, 3, 2, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 2, 2, 3, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 3, 2, 2, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 3, 2, 3, 3, 2, 2, 3, 4, 3, 2, 3, 3, 3, 3, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 3, 3, 3, 3, 4, 3, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 2, 2, 2, 3, 3, 3, 3, 4, 4, 2, 2, 3, 3, 3, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 2, 3, 3, 3, 1, 2, 3, 4, 2, 2, 3, 3, 3, 2, 3, 4, 3, 2, 3, 3, 2, 2, 3, 4, 3, 3, 3, 3, 4, 2, 3, 4, 2, 2, 3, 3, 2, 3, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 3, 3, 3, 3, 3, 2, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 3, 3, 2, 3, 2, 2, 3, 4, 3, 3, 2, 3, 3, 3, 3, 4, 2, 3, 3, 3, 2, 2, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 4, 3, 3, 3, 2, 2, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 3, 2, 3, 3, 3, 3, 3, 4, 3, 1, 2, 3, 3, 2, 3, 4, 2, 3, 2, 3, 2, 3, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 3, 2, 2, 3, 2, 2, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 3, 3, 3, 3, 3, 3, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 4, 2, 2, 3, 3, 2, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 3, 3, 3, 3, 2, 2, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 4, 3, 2, 3, 3, 2, 3, 4, 3, 3, 3, 3, 4, 3, 3, 4, 2, 3, 2, 3, 2, 3, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 3, 2, 3, 3, 3, 3, 3, 4, 3, 2, 2, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 2, 2, 3, 3, 3, 2, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 4, 2, 3, 3, 2, 3, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 3, 2, 2, 3, 2, 3, 3, 4, 3, 1, 2, 3, 4, 2, 3, 4, 2, 3, 2, 3, 2, 3, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 3, 2, 2, 3, 2, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 2, 3, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 3, 3, 2, 3, 3, 3, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 4, 2, 2, 3, 2, 3, 3, 4, 3, 3, 3, 3, 4, 2, 3, 4, 3, 3, 3, 3, 2, 2, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 2, 3, 3, 3, 1, 2, 3, 4, 2, 2, 3, 3, 3, 2, 3, 4, 3, 2, 3, 3, 2, 3, 3, 4, 3, 3, 3, 3, 4, 2, 3, 4, 3, 3, 2, 3, 2, 2, 3, 4, 2, 2, 3, 3, 3, 2, 3, 4, 3, 3, 2, 3, 2, 2, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 3, 2, 3, 3, 2, 3, 3, 4, 3, 2, 3, 3, 3, 2, 3, 4, 4, 3, 3, 3, 3, 2, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 3, 2, 3, 3, 2, 3, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 2, 2, 3, 3, 3, 2, 3, 4, 3, 2, 2, 3, 4, 2, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 3, 1, 2, 3, 2, 2, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 4, 2, 2, 3, 3, 3, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 3, 3, 2, 3, 3, 3, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 4, 2, 3, 3, 2, 3, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 2, 2, 2, 3, 3, 2, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 3, 3, 3, 3, 2, 2, 3, 4, 3, 3, 3, 3, 4, 3, 3, 4, 3, 2, 3, 3, 2, 3, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 3, 3, 3, 3, 3, 3, 3, 4, 3, 3, 3, 3, 4, 3, 3, 4, 1, 2, 2, 3, 2, 2, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 2, 3, 2, 3, 2, 3, 3, 4, 3, 2, 2, 3, 4, 2, 3, 4, 3, 3, 2, 3, 2, 3, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 4, 2, 2, 3, 3, 2, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 2, 2, 3, 3, 2, 3, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 3, 2, 3, 3, 2, 3, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 3, 2, 3, 3, 2, 3, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 3, 3, 3, 4, 2, 1, 2, 3, 3, 2, 3, 4, 3, 2, 2, 3, 4, 2, 3, 4, 3, 2, 3, 3, 3, 3, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 4, 3, 3, 3, 2, 2, 3, 4, 3, 3, 3, 3, 4, 3, 3, 4, 3, 3, 2, 3, 2, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 2, 2, 2, 3, 3, 2, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 3, 3, 3, 3, 4, 2, 3, 4, 2, 2, 3, 3, 2, 2, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 3, 3, 2, 3, 3, 3, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 3, 2, 3, 3, 1, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 4, 3, 2, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 3, 3, 2, 3, 2, 3, 3, 4, 2, 2, 3, 3, 3, 2, 3, 4, 3, 2, 3, 3, 2, 2, 3, 4, 3, 3, 3, 3, 4, 3, 3, 4, 2, 2, 3, 3, 2, 3, 3, 4, 3, 2, 3, 3, 3, 3, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 3, 3, 3, 3, 4, 3, 3, 4, 4, 2, 2, 3, 3, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 3, 3, 2, 3, 3, 3, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 4, 2, 2, 3, 2, 3, 3, 4, 3, 1, 2, 3, 4, 2, 3, 4, 3, 3, 2, 3, 2, 3, 3, 4, 3, 2, 3, 3, 3, 2, 3, 4, 2, 3, 2, 3, 2, 2, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 3, 3, 2, 3, 2, 2, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 3, 3, 3, 3, 2, 3, 3, 4, 3, 2, 2, 3, 4, 2, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 3, 3, 2, 3, 3, 3, 3, 4, 3, 2, 2, 3, 2, 2, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 3, 2, 3, 3, 2, 2, 3, 4, 3, 2, 3, 3, 3, 2, 3, 4, 4, 3, 2, 3, 3, 2, 3, 4, 3, 3, 3, 3, 4, 3, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 1, 2, 3, 3, 2, 3, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 3, 2, 3, 3, 2, 2, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 3, 2, 3, 3, 3, 3, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 3, 2, 2, 3, 2, 2, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 4, 3, 3, 3, 2, 2, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 4, 3, 3, 3, 3, 3, 3, 4, 3, 2, 3, 3, 3, 3, 3, 4, 2, 2, 2, 3, 3, 3, 3, 4, 3, 2, 2, 3, 4, 2, 3, 4, 2, 3, 3, 3, 2, 3, 3, 4, 3, 1, 2, 3, 3, 2, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 3, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 2, 3, 3, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 4, 2, 2, 3, 3, 2, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 3, 3, 3, 3, 3, 3, 3, 4, 3, 2, 3, 3, 3, 2, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 3, 3, 3, 3, 4, 3, 3, 4, 3, 3, 2, 3, 2, 2, 3, 4, 2, 2, 2, 3, 3, 3, 3, 4, 3, 2, 2, 3, 2, 3, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 4, 3, 2, 3, 1, 2, 3, 4, 2, 2, 3, 3, 3, 2, 3, 4, 3, 3, 2, 3, 2, 2, 3, 4, 3, 3, 3, 3, 4, 2, 3, 4, 3, 2, 3, 3, 3, 3, 3, 4, 2, 2, 2, 3, 3, 2, 3, 4, 4, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 3, 2, 3, 3, 2, 3, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 3, 2, 3, 3, 3, 2, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 3, 3, 3, 3, 2, 2, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 2, 3, 3, 3, 2, 3, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 2, 3, 3, 3, 2, 2, 3, 4, 3, 3, 3, 3, 4, 3, 3, 4, 3, 1, 2, 3, 3, 2, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 4, 2, 3, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 2, 2, 2, 3, 3, 2, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 3, 3, 2, 3, 2, 3, 3, 4, 3, 3, 3, 3, 4, 2, 3, 4, 2, 2, 3, 3, 3, 2, 3, 4, 3, 3, 3, 3, 3, 2, 3, 4, 3, 3, 2, 3, 3, 3, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 3, 2, 2, 3, 2, 2, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 2, 2, 2, 3, 3, 3, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 4, 2, 3, 3, 2, 2, 3, 4, 3, 3, 3, 3, 4, 2, 3, 4, 1, 2, 3, 3, 2, 3, 3, 4, 2, 2, 2, 3, 3, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 3, 3, 2, 3, 2, 2, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 2, 2, 3, 3, 2, 2, 3, 4, 3, 3, 3, 3, 4, 3, 3, 4, 3, 2, 2, 3, 2, 3, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 4, 3, 2, 3, 2, 3, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 3, 3, 3, 3, 3, 3, 3, 4, 2, 3, 3, 3, 2, 3, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 2, 1, 2, 3, 3, 2, 3, 4, 2, 2, 2, 3, 3, 3, 3, 4, 3, 2, 3, 3, 3, 2, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 4, 3, 3, 3, 2, 2, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 3, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 4, 2, 2, 3, 3, 3, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 2, 3, 2, 3, 2, 2, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 3, 2, 3, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 3, 2, 3, 3, 3, 3, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 3, 2, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 3, 3, 2, 3, 1, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 2, 2, 3, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 3, 3, 3, 3, 3, 2, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 4, 3, 2, 3, 2, 2, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 2, 3, 2, 3, 2, 3, 3, 4, 3, 2, 3, 3, 3, 3, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 3, 3, 3, 3, 4, 2, 3, 4, 3, 2, 3, 3, 3, 3, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 2, 3, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 3, 2, 2, 3, 2, 2, 3, 4, 3, 3, 3, 3, 4, 2, 3, 4, 3, 3, 3, 3, 2, 2, 3, 4, 3, 1, 2, 3, 3, 2, 3, 4, 4, 3, 2, 3, 3, 3, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 2, 2, 2, 3, 3, 2, 3, 4, 2, 2, 3, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 3, 3, 3, 3, 2, 2, 3, 4, 3, 2, 3, 3, 3, 2, 3, 4, 3, 2, 2, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 2, 2, 3, 3, 2, 3, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 3, 3, 2, 3, 2, 2, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 4, 2, 3, 3, 3, 3, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 3, 3, 3, 3, 3, 2, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 3, 2, 2, 3, 4, 2, 3, 4, 2, 3, 3, 3, 2, 3, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 3, 3, 2, 3, 2, 2, 3, 4, 3, 3, 3, 3, 4, 3, 3, 4, 4, 2, 3, 3, 2, 2, 3, 4, 3, 3, 2, 3, 3, 3, 3, 4, 2, 2, 3, 3, 2, 3, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 3, 2, 3, 3, 3, 2, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 4, 3, 2, 3, 2, 2, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 4, 3, 3, 3, 3, 2, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 2, 3, 2, 3, 2, 3, 3, 4, 2, 2, 3, 3, 3, 2, 3, 4, 3, 3, 2, 3, 2, 3, 3, 4, 3, 1, 2, 3, 4, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 3, 3, 2, 3, 2, 2, 3, 4, 3, 3, 3, 3, 4, 2, 3, 4, 3, 2, 3, 3, 3, 3, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 4, 2, 3, 3, 3, 3, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 3, 2, 2, 3, 2, 2, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 3, 3, 3, 3, 3, 3, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 3, 2, 3, 3, 3, 2, 3, 4, 2, 3, 3, 3, 2, 2, 3, 4, 3, 3, 3, 3, 4, 2, 3, 4, 3, 2, 2, 3, 1, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 4, 3, 3, 3, 2, 3, 3, 4, 3, 2, 2, 3, 4, 2, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 3, 3, 2, 3, 2, 2, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 2, 2, 3, 3, 2, 2, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 2, 2, 3, 3, 2, 3, 3, 4, 2, 2, 3, 3, 3, 2, 3, 4, 3, 3, 3, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 3, 3, 2, 3, 3, 3, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 4, 2, 2, 3, 2, 2, 3, 4, 3, 3, 3, 3, 4, 2, 3, 4, 3, 3, 3, 3, 2, 3, 3, 4, 3, 2, 3, 3, 3, 2, 3, 4, 3, 1, 2, 3, 3, 2, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 3, 3, 3, 3, 2, 2, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 4, 3, 2, 3, 3, 2, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 3, 2, 2, 3, 2, 3, 3, 4, 3, 3, 3, 3, 3, 3, 3, 4, 4, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 3, 2, 3, 3, 2, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 2, 2, 3, 3, 3, 2, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 3, 3, 2, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 1, 2, 3, 3, 2, 3, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 3, 3, 2, 3, 2, 3, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 4, 2, 2, 3, 2, 3, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 3, 2, 3, 3, 3, 2, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 2, 2, 3, 3, 2, 3, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 3, 2, 3, 3, 3, 2, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 2, 3, 3, 3, 2, 2, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 3, 3, 3, 3, 3, 3, 3, 4, 3, 2, 3, 3, 3, 3, 3, 4, 4, 1, 2, 3, 3, 2, 3, 4, 3, 2, 2, 3, 4, 2, 3, 4, 4, 2, 2, 3, 2, 3, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 3, 3, 2, 3, 2, 2, 3, 4, 3, 3, 3, 3, 4, 3, 3, 4, 3, 2, 2, 3, 2, 3, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 3, 2, 3, 3, 2, 3, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 3, 2, 3, 3, 2, 2, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 3, 2, 3, 3, 2, 3, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 4, 3, 3, 3, 3, 2, 3, 4, 3, 3, 3, 3, 4, 3, 3, 4, 3, 2, 2, 3, 2, 2, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 2, 2, 2, 3, 3, 3, 3, 4, 3, 2, 2, 3, 4, 2, 3, 4, 3, 3, 2, 3, 1, 2, 3, 4, 2, 2, 3, 3, 3, 2, 3, 4, 3, 3, 2, 3, 2, 2, 3, 4, 3, 3, 3, 3, 4, 2, 3, 4, 4, 3, 3, 3, 3, 3, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 2, 2, 2, 3, 3, 2, 3, 4, 3, 3, 3, 3, 4, 3, 3, 4, 3, 2, 3, 3, 2, 3, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 4, 2, 3, 3, 2, 2, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 3, 2, 2, 3, 2, 3, 3, 4, 3, 3, 3, 3, 4, 2, 3, 4, 2, 3, 2, 3, 2, 3, 3, 4, 3, 2, 3, 3, 3, 2, 3, 4, 3, 3, 2, 3, 2, 2, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 3, 3, 2, 3, 3, 3, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 2, 3, 3, 4, 3, 1, 2, 3, 4, 2, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 2, 2, 2, 3, 3, 3, 3, 4, 4, 3, 2, 3, 3, 3, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 2, 2, 3, 3, 2, 2, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 2, 2, 2, 3, 2, 2, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 3, 2, 3, 3, 3, 3, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 3, 3, 3, 3, 2, 2, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 3, 3, 3, 3, 2, 3, 3, 4, 2, 2, 3, 3, 3, 2, 3, 4, 4, 2, 2, 3, 3, 3, 3, 4, 3, 3, 3, 3, 4, 3, 3, 4, 3, 3, 2, 3, 2, 3, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 1, 2, 3, 3, 2, 2, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 3, 2, 3, 3, 2, 2, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 3, 2, 3, 3, 2, 3, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 3, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 4, 3, 3, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 2, 2, 2, 3, 3, 3, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 3, 3, 3, 3, 4, 2, 3, 4, 2, 2, 3, 3, 2, 3, 3, 4, 3, 3, 3, 3, 3, 2, 3, 4, 3, 3, 3, 3, 3, 2, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 4, 2, 2, 3, 2, 3, 3, 4, 3, 1, 2, 3, 3, 2, 3, 4, 2, 3, 2, 3, 2, 3, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 3, 3, 2, 3, 2, 2, 3, 4, 3, 2, 3, 3, 3, 2, 3, 4, 4, 2, 3, 3, 2, 2, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 2, 2, 2, 3, 3, 3, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 3, 3, 3, 4, 3, 2, 2, 3, 4, 2, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 2, 3, 3, 3, 2, 3, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 3, 2, 3, 3, 3, 3, 3, 4, 3, 3, 2, 3, 3, 3, 3, 4, 4, 3, 2, 3, 2, 2, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 3, 2, 3, 3, 1, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 2, 3, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 2, 2, 3, 3, 3, 2, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 3, 3, 2, 3, 2, 2, 3, 4, 3, 3, 3, 3, 4, 2, 3, 4, 3, 3, 3, 3, 2, 3, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 3, 3, 3, 3, 4, 3, 3, 4, 3, 2, 3, 3, 3, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 4, 2, 3, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 3, 3, 2, 3, 3, 3, 3, 4, 3, 2, 3, 3, 3, 2, 3, 4, 3, 3, 2, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 2, 2, 3, 3, 2, 3, 3, 4, 2, 2, 3, 3, 3, 2, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 3, 3, 3, 3, 4, 3, 3, 4, 3, 1, 2, 3, 2, 2, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 3, 3, 3, 3, 3, 2, 3, 4, 3, 2, 3, 3, 3, 3, 3, 4, 4, 3, 2, 3, 2, 2, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 3, 2, 2, 3, 2, 3, 3, 4, 3, 3, 2, 3, 3, 3, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 3, 3, 2, 3, 2, 2, 3, 4, 3, 3, 3, 3, 3, 2, 3, 4, 3, 2, 3, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 4, 2, 3, 3, 3, 2, 3, 4, 2, 2, 2, 3, 3, 3, 3, 4, 3, 2, 3, 3, 2, 2, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 3, 3, 3, 3, 2, 2, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 4, 3, 3, 3, 3, 3, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 1, 2, 3, 3, 2, 2, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 2, 3, 3, 3, 2, 3, 3, 4, 3, 2, 2, 3, 4, 2, 3, 4, 2, 3, 2, 3, 2, 3, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 3, 3, 2, 3, 2, 3, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 4, 3, 3, 3, 2, 2, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 3, 3, 3, 3, 3, 3, 3, 4, 2, 3, 3, 3, 2, 2, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 2, 2, 2, 3, 3, 3, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 3, 3, 3, 3, 2, 2, 3, 4, 3, 3, 3, 3, 4, 3, 3, 4, 3, 1, 2, 3, 2, 2, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 2, 3, 3, 4, 3, 2, 2, 3, 4, 2, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 4, 2, 2, 3, 3, 2, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 2, 2, 3, 3, 3, 2, 3, 4, 3, 3, 3, 3, 3, 3, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 3, 2, 2, 3, 2, 2, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 3, 2, 2, 3, 2, 3, 3, 4, 3, 2, 2, 3, 4, 2, 3, 4, 2, 3, 3, 3, 2, 3, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 3, 2, 2, 3, 2, 3, 3, 4, 3, 3, 3, 3, 4, 2, 3, 4, 3, 3, 3, 3, 2, 3, 3, 4, 3, 2, 2, 3, 3, 3, 3, 4, 4, 3, 2, 3, 3, 3, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 3, 2, 2, 3, 1, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 2, 3, 3, 3, 2, 2, 3, 4, 3, 3, 2, 3, 4, 2, 3, 4, 3, 3, 2, 3, 3, 3, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 4, 2, 3, 4, 4, 2, 3, 3, 2, 3, 3, 4, 3, 2, 3, 3, 3, 2, 3, 4, 2, 3, 3, 3, 2, 2, 3, 4, 3, 2, 3, 3, 4, 3, 3, 4, 3, 2, 2, 3, 2, 2, 3, 4, 2, 3, 3, 3, 3, 3, 3, 4, 4, 3, 3, 3, 3, 3, 3, 4, 3, 2, 2, 3, 4, 2, 3, 4, 3, 3, 3, 3, 3, 2, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 3, 2, 3, 3, 2, 2, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 2, 3, 3, 3, 2, 3, 3, 4, 3, 2, 2, 3, 3, 2, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 3, 3, 3, 3, 4, 3, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 2, 1, 2, 3, 3, 2, 3, 4, 2, 2, 2, 3, 3, 3, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 2, 2, 3, 3, 3, 2, 3, 4, 4, 2, 3, 3, 3, 3, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 3, 2, 3, 3, 2, 3, 3, 4, 2, 2, 2, 3, 3, 3, 3, 4, 2, 2, 2, 3, 3, 3, 3, 4, 3, 2, 2, 3, 4, 3, 3, 4, 3, 3, 3, 3, 2, 2, 3, 4, 2, 3, 2, 3, 3, 2, 3, 4, 3, 3, 3, 3, 2, 3, 3, 4, 3, 3, 2, 3, 4, 3, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 2, 2, 3, 3, 3, 3, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 3, 2, 2, 3, 4, 2, 3, 4, 3, 2, 3, 3, 3, 3, 3, 4, 3, 3, 2, 3, 3, 2, 3, 4, 4, 3, 2, 3, 2, 2, 3, 4, 3, 3, 3, 3, 4, 2, 3, 4, 4, 2, 2, 3, 3, 3, 3, 4, 2, 3, 3, 3, 3, 2, 3, 4, 1]
		array[0] = 1
		array[1] = 2
		array_n = len(array)
		for i in range(array_n, n):
			if self.as_a_perfect_square(i + 1):
				array[array_n] = 1
				array_n += 1
			else:
				array[array_n] = self.min_perfect_square(i, array)
				array_n += 1
		return array[n - 1]