

"""simple docstring"""



def  _snake_case     (    UpperCAmelCase_  :					int = 100_0000			):
     A__										=  [i - 1 for i in range(limit + 1			)]

     for i in range(2					,   limit + 1			):
          if phi[i] == i - 1:
               for j in range(2 * i					,   limit + 1					,   UpperCAmelCase_			):
                    phi[j] -= phi[j] // i

     return sum(phi[2 : limit + 1]			)


if __name__ == "__main__":
 print(solution())








"""simple docstring"""



import math
import sys





def  _snake_case     (    UpperCAmelCase_  :					int			):
     if number != int(UpperCAmelCase_			):
          raise ValueError("""the value of input must be a natural number"""			)
     if number < 0:
          raise ValueError("""the value of input must not be a negative number"""			)
     if number == 0:
          return 1
     A__										=  [-1] * (number + 1)
     A__										=  0
     for i in range(1					,   number + 1			):
          A__										=  sys.maxsize
          A__										=  int(math.sqrt(UpperCAmelCase_			)			)
          for j in range(1					,   root + 1			):
               A__										=  1 + answers[i - (j**2)]
               A__										=  min(UpperCAmelCase_					,   UpperCAmelCase_			)
          A__										=  answer
     return answers[number]


if __name__ == "__main__":
 import doctest

 doctest.testmod()






