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: interview

Starter code:

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

Solutions:
class Solution:
     def numSquares(self, n):
         """
         :type n: int
         :rtype: int
         """
         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):
         """
         :type n: int
         :rtype: int
         """
         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):
         """
         四平方和定理
         :type n: int
         :rtype: int
         """
         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):
         """
         :type n: int
         :rtype: int
         """
         import math
         while n%4 == 0:
             n = n/4
         if n%8 == 7:
             return 4
         if round(math.sqrt(n))**2 == n:
             return 1
         #接下来判断n是否由两个完全平方数的和组成
         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]