

from __future__ import annotations

from fractions import Fraction
from math import gcd, sqrt






def 					__lowercase      (     _A			)     ->						bool:
      SCREAMING_SNAKE_CASE :      List[str]       =   int(number**0.5			)
      return number == sq * sq






def 					__lowercase      (     _A						,    _A						,    _A						,    _A						,    _A						,    _A			)     ->						tuple[int, int]:
      SCREAMING_SNAKE_CASE :      Optional[int]       =   x_num * y_den * z_den + y_num * x_den * z_den + z_num * x_den * y_den
      SCREAMING_SNAKE_CASE :      Any       =   x_den * y_den * z_den
      SCREAMING_SNAKE_CASE :      Dict       =   gcd(_A						,    _A			)
      top //= hcf
      bottom //= hcf
      return top, bottom






def 					__lowercase      (     _A = 35			)     ->						int:
      SCREAMING_SNAKE_CASE :      Union[str, Any]       =   set()
      SCREAMING_SNAKE_CASE :      int       =   42
      SCREAMING_SNAKE_CASE :      Any       =   Fraction(0			)
      SCREAMING_SNAKE_CASE :      str       =   42

      for x_num in range(1						,    order + 1			):
            for x_den in range(x_num + 1						,    order + 1			):
                  for y_num in range(1						,    order + 1			):
                        for y_den in range(y_num + 1						,    order + 1			):
                              # n=1
                              SCREAMING_SNAKE_CASE :      Optional[Any]       =   x_num * y_den + x_den * y_num
                              SCREAMING_SNAKE_CASE :      List[Any]       =   x_den * y_den
                              SCREAMING_SNAKE_CASE :      Dict       =   gcd(_A						,    _A			)
                              z_num //= hcf
                              z_den //= hcf
                              if 0 < z_num < z_den <= order:
                                    SCREAMING_SNAKE_CASE :      Optional[Any]       =   add_three(
                                        _A						,    _A						,    _A						,    _A						,    _A						,    _A			)
                                    unique_s.add(_A			)

                              # n=2
                              SCREAMING_SNAKE_CASE :      str       =   (
                                  x_num * x_num * y_den * y_den + x_den * x_den * y_num * y_num
                              )
                              SCREAMING_SNAKE_CASE :      Union[str, Any]       =   x_den * x_den * y_den * y_den
                              if is_sq(_A			) and is_sq(_A			):
                                    SCREAMING_SNAKE_CASE :      List[Any]       =   int(sqrt(_A			)			)
                                    SCREAMING_SNAKE_CASE :      Optional[int]       =   int(sqrt(_A			)			)
                                    SCREAMING_SNAKE_CASE :      Optional[int]       =   gcd(_A						,    _A			)
                                    z_num //= hcf
                                    z_den //= hcf
                                    if 0 < z_num < z_den <= order:
                                          SCREAMING_SNAKE_CASE :      List[Any]       =   add_three(
                                              _A						,    _A						,    _A						,    _A						,    _A						,    _A			)
                                          unique_s.add(_A			)

                    # n=-1
                              SCREAMING_SNAKE_CASE :      Any       =   x_num * y_num
                              SCREAMING_SNAKE_CASE :      str       =   x_den * y_num + x_num * y_den
                              SCREAMING_SNAKE_CASE :      Optional[int]       =   gcd(_A						,    _A			)
                              z_num //= hcf
                              z_den //= hcf
                              if 0 < z_num < z_den <= order:
                                    SCREAMING_SNAKE_CASE :      str       =   add_three(
                                        _A						,    _A						,    _A						,    _A						,    _A						,    _A			)
                                    unique_s.add(_A			)

                              # n=2
                              SCREAMING_SNAKE_CASE :      List[str]       =   x_num * x_num * y_num * y_num
                              SCREAMING_SNAKE_CASE :      str       =   (
                                  x_den * x_den * y_num * y_num + x_num * x_num * y_den * y_den
                              )
                              if is_sq(_A			) and is_sq(_A			):
                                    SCREAMING_SNAKE_CASE :      Dict       =   int(sqrt(_A			)			)
                                    SCREAMING_SNAKE_CASE :      str       =   int(sqrt(_A			)			)
                                    SCREAMING_SNAKE_CASE :      Optional[Any]       =   gcd(_A						,    _A			)
                                    z_num //= hcf
                                    z_den //= hcf
                                    if 0 < z_num < z_den <= order:
                                          SCREAMING_SNAKE_CASE :      List[str]       =   add_three(
                                              _A						,    _A						,    _A						,    _A						,    _A						,    _A			)
                                          unique_s.add(_A			)

      for num, den in unique_s:
            total += Fraction(_A						,    _A			)

      return total.denominator + total.numerator


if __name__ == "__main__":
   print(F"""{solution() = }""")







def 					__lowercase      (     _A			)     ->						list[int]:
      SCREAMING_SNAKE_CASE :      int       =   [0 for i in range(len(_A			)			)]

      # initialize interval's left pointer and right pointer
      SCREAMING_SNAKE_CASE     ,	SCREAMING_SNAKE_CASE :      Dict       =   0, 0

      for i in range(1						,    len(_A			)			):
            # case when current index is inside the interval
            if i <= right_pointer:
                  SCREAMING_SNAKE_CASE :      Any       =   min(right_pointer - i + 1						,    z_result[i - left_pointer]			)
                  SCREAMING_SNAKE_CASE :      Optional[Any]       =   min_edge

            while go_next(_A						,    _A						,    _A			):
                  z_result[i] += 1

            # if new index's result gives us more right interval,
            # we've to update left_pointer and right_pointer
            if i + z_result[i] - 1 > right_pointer:
                  SCREAMING_SNAKE_CASE     ,	SCREAMING_SNAKE_CASE :      List[Any]       =   i, i + z_result[i] - 1

      return z_result






def 					__lowercase      (     _A						,    _A						,    _A			)     ->						bool:
      return i + z_result[i] < len(_A			) and s[z_result[i]] == s[i + z_result[i]]






def 					__lowercase      (     _A						,    _A			)     ->						int:
      SCREAMING_SNAKE_CASE :      Any       =   0
      # concatenate 'pattern' and 'input_str' and call z_function
      # with concatenated string
      SCREAMING_SNAKE_CASE :      List[Any]       =   z_function(pattern + input_str			)

      for val in z_result:
            # if value is greater then length of the pattern string
            # that means this index is starting position of substring
            # which is equal to pattern string
            if val >= len(_A			):
                  answer += 1

      return answer


if __name__ == "__main__":
  import doctest

  doctest.testmod()




