



"""simple docstring"""







from typing import Any

def     UpperCamelCase_   (   lowerCAmelCase__				:    list   ,       lowerCAmelCase__				:    list   ,       lowerCAmelCase__				:    dict   ,       lowerCAmelCase__				:    dict   ,       lowerCAmelCase__				:    dict   ,       )						->       list:

  """simple docstring"""




  _validation(
      lowerCAmelCase__   ,       lowerCAmelCase__   ,       lowerCAmelCase__   ,       lowerCAmelCase__   ,       lowerCAmelCase__   ,       )
  # Creates data structures and fill initial step
  lowerCAmelCase_       :    dict								=			{}
  lowerCAmelCase_       :    dict								=			{}
  for state in states_space:
    lowerCAmelCase_       :    Union[str, Any]								=			observations_space[0]
    lowerCAmelCase_       :    List[Any]								=			(
        initial_probabilities[state] * emission_probabilities[state][observation]
    )
    lowerCAmelCase_       :    Any								=			None

  # Fills the data structure with the probabilities of
  # different transitions and pointers to previous states
  for o in range(1   ,       len(lowerCAmelCase__						)						):
    lowerCAmelCase_       :    Dict								=			observations_space[o]
    lowerCAmelCase_       :    Union[str, Any]								=			observations_space[o - 1]
    for state in states_space:
      # Calculates the argmax for probability function
      lowerCAmelCase_       :    Any								=			''
      lowerCAmelCase_       :    Union[str, Any]								=			-1
      for k_state in states_space:
        lowerCAmelCase_       :    int								=			(
            probabilities[(k_state, prior_observation)]
            * transition_probabilities[k_state][state]
            * emission_probabilities[state][observation]
        )
        if probability > max_probability:
          lowerCAmelCase_       :    int								=			probability
          lowerCAmelCase_       :    Any								=			k_state

            # Update probabilities and pointers dicts
      lowerCAmelCase_       :    List[Any]								=			(
          probabilities[(arg_max, prior_observation)]
          * transition_probabilities[arg_max][state]
          * emission_probabilities[state][observation]
      )

      lowerCAmelCase_       :    Dict								=			arg_max

    # The final observation
  lowerCAmelCase_       :    int								=			observations_space[len(lowerCAmelCase__						) - 1]

  # argmax for given final observation
  lowerCAmelCase_       :    Optional[Any]								=			''
  lowerCAmelCase_       :    Any								=			-1
  for k_state in states_space:
    lowerCAmelCase_       :    List[Any]								=			probabilities[(k_state, final_observation)]
    if probability > max_probability:
      lowerCAmelCase_       :    Union[str, Any]								=			probability
      lowerCAmelCase_       :    Union[str, Any]								=			k_state
  lowerCAmelCase_       :    Any								=			arg_max

  # Process pointers backwards
  lowerCAmelCase_       :    Dict								=			last_state
  lowerCAmelCase_       :    Union[str, Any]								=			[]
  for o in range(len(lowerCAmelCase__						) - 1   ,       -1   ,       -1						):
    result.append(lowerCAmelCase__						)
    lowerCAmelCase_       :    Union[str, Any]								=			pointers[previous, observations_space[o]]
  result.reverse()

  return result

def     UpperCamelCase_   (   lowerCAmelCase__				:    Any   ,       lowerCAmelCase__				:    Any   ,       lowerCAmelCase__				:    Any   ,       lowerCAmelCase__				:    Any   ,       lowerCAmelCase__				:    Any   ,       )						->       None:

  """simple docstring"""




  _validate_not_empty(
      lowerCAmelCase__   ,       lowerCAmelCase__   ,       lowerCAmelCase__   ,       lowerCAmelCase__   ,       lowerCAmelCase__   ,       )
  _validate_lists(lowerCAmelCase__   ,       lowerCAmelCase__						)
  _validate_dicts(
      lowerCAmelCase__   ,       lowerCAmelCase__   ,       lowerCAmelCase__						)

def     UpperCamelCase_   (   lowerCAmelCase__				:    Any   ,       lowerCAmelCase__				:    Any   ,       lowerCAmelCase__				:    Any   ,       lowerCAmelCase__				:    Any   ,       lowerCAmelCase__				:    Any   ,       )						->       None:

  """simple docstring"""




  if not all(
      [
          observations_space,
          states_space,
          initial_probabilities,
          transition_probabilities,
          emission_probabilities,
      ]						):
    raise ValueError('There\'s an empty parameter'						)

def     UpperCamelCase_   (   lowerCAmelCase__				:    Any   ,       lowerCAmelCase__				:    Any						)						->       None:

  """simple docstring"""




  _validate_list(lowerCAmelCase__   ,       'observations_space'						)
  _validate_list(lowerCAmelCase__   ,       'states_space'						)

def     UpperCamelCase_   (   lowerCAmelCase__				:    Any   ,       lowerCAmelCase__				:    str						)						->       None:

  """simple docstring"""




  if not isinstance(_object   ,       lowerCAmelCase__						):
    lowerCAmelCase_       :    Optional[int]								=			f"{var_name} must be a list"
    raise ValueError(lowerCAmelCase__						)
  else:
    for x in _object:
      if not isinstance(lowerCAmelCase__   ,       lowerCAmelCase__						):
        lowerCAmelCase_       :    Dict								=			f"{var_name} must be a list of strings"
        raise ValueError(lowerCAmelCase__						)

def     UpperCamelCase_   (   lowerCAmelCase__				:    Any   ,       lowerCAmelCase__				:    Any   ,       lowerCAmelCase__				:    Any   ,       )						->       None:

  """simple docstring"""




  _validate_dict(lowerCAmelCase__   ,       'initial_probabilities'   ,       lowerCAmelCase__						)
  _validate_nested_dict(lowerCAmelCase__   ,       'transition_probabilities'						)
  _validate_nested_dict(lowerCAmelCase__   ,       'emission_probabilities'						)

def     UpperCamelCase_   (   lowerCAmelCase__				:    Any   ,       lowerCAmelCase__				:    str						)						->       None:

  """simple docstring"""




  _validate_dict(_object   ,       lowerCAmelCase__   ,       lowerCAmelCase__						)
  for x in _object.values():
    _validate_dict(lowerCAmelCase__   ,       lowerCAmelCase__   ,       lowerCAmelCase__   ,       lowerCAmelCase__						)

def     UpperCamelCase_   (   lowerCAmelCase__				:    Any   ,       lowerCAmelCase__				:    str   ,       lowerCAmelCase__				:    type   ,       lowerCAmelCase__				:    bool = False						)						->       None:

  """simple docstring"""




  if not isinstance(_object   ,       lowerCAmelCase__						):
    lowerCAmelCase_       :    int								=			f"{var_name} must be a dict"
    raise ValueError(lowerCAmelCase__						)
  if not all(isinstance(lowerCAmelCase__   ,       lowerCAmelCase__						) for x in _object						):
    lowerCAmelCase_       :    List[Any]								=			f"{var_name} all keys must be strings"
    raise ValueError(lowerCAmelCase__						)
  if not all(isinstance(lowerCAmelCase__   ,       lowerCAmelCase__						) for x in _object.values()						):
    lowerCAmelCase_       :    Tuple								=			'nested dictionary ' if nested else ''
    lowerCAmelCase_       :    int								=			f"{var_name} {nested_text}all values must be {value_type.__name__}"
    raise ValueError(lowerCAmelCase__						)


if __name__ == "__main__":
     from doctest import testmod

     testmod()










"""simple docstring"""







from __future__ import annotations

from fractions import Fraction
from math import gcd, sqrt

def     UpperCamelCase_   (   lowerCAmelCase__				:    int						)						->       bool:

  """simple docstring"""




  lowerCAmelCase_       :    int								=			int(number**0.5						)
  return number == sq * sq

def     UpperCamelCase_   (   lowerCAmelCase__				:    int   ,       lowerCAmelCase__				:    int   ,       lowerCAmelCase__				:    int   ,       lowerCAmelCase__				:    int   ,       lowerCAmelCase__				:    int   ,       lowerCAmelCase__				:    int						)						->       tuple[int, int]:

  """simple docstring"""




  lowerCAmelCase_       :    int								=			x_num * y_den * z_den + y_num * x_den * z_den + z_num * x_den * y_den
  lowerCAmelCase_       :    int								=			x_den * y_den * z_den
  lowerCAmelCase_       :    int								=			gcd(lowerCAmelCase__   ,       lowerCAmelCase__						)
  top //= hcf
  bottom //= hcf
  return top, bottom

def     UpperCamelCase_   (   lowerCAmelCase__				:    int = 35						)						->       int:

  """simple docstring"""




  lowerCAmelCase_       :    set								=			set()
  lowerCAmelCase_       :    int
  lowerCAmelCase_       :    Fraction								=			Fraction(0						)
  lowerCAmelCase_       :    tuple[int, int]

  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
          lowerCAmelCase_       :    str								=			x_num * y_den + x_den * y_num
          lowerCAmelCase_       :    int								=			x_den * y_den
          lowerCAmelCase_       :    int								=			gcd(lowerCAmelCase__   ,       lowerCAmelCase__						)
          z_num //= hcf
          z_den //= hcf
          if 0 < z_num < z_den <= order:
            lowerCAmelCase_       :    List[str]								=			add_three(
                lowerCAmelCase__   ,       lowerCAmelCase__   ,       lowerCAmelCase__   ,       lowerCAmelCase__   ,       lowerCAmelCase__   ,       lowerCAmelCase__						)
            unique_s.add(lowerCAmelCase__						)

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

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

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

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

  return total.denominator + total.numerator


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





