


'''simple docstring'''

from abc import ABC, abstractmethod
from typing import List, Optional





class      snake_case    (    lowercase			):





  """simple docstring"""




  def __init__(    self     ):







   """simple docstring"""
   # test for the above condition
   self.test()






  def   snake_case		(    self     ):







   """simple docstring"""
   lowerCamelCase_      =  0
   lowerCamelCase_      =  False
   while not completed:
    if counter == 1:
     self.reset()
    lowerCamelCase_      =  self.advance()
    if not self.does_advance(UpperCamelCase     ):
     raise Exception(
         "Custom Constraint is not defined correctly. self.does_advance(self.advance()) must be true."     )

    lowerCamelCase_ ,lowerCamelCase_ ,lowerCamelCase_      =  self.update(UpperCamelCase     )
    counter += 1

    if counter > 1_0000:
     raise Exception("update() does not fulfill the constraint."     )

   if self.remaining() != 0:
    raise Exception("Custom Constraint is not defined correctly."     )






  @abstractmethod
  def   snake_case		(    self     ):







   """simple docstring"""
   raise NotImplementedError(
       f'''{self.__class__} is an abstract class. Only classes inheriting this class can be called.'''     )






  @abstractmethod
  def   snake_case		(    self			,  UpperCamelCase     ):







   """simple docstring"""
   raise NotImplementedError(
       f'''{self.__class__} is an abstract class. Only classes inheriting this class can be called.'''     )






  @abstractmethod
  def   snake_case		(    self			,  UpperCamelCase     ):







   """simple docstring"""
   raise NotImplementedError(
       f'''{self.__class__} is an abstract class. Only classes inheriting this class can be called.'''     )






  @abstractmethod
  def   snake_case		(    self     ):







   """simple docstring"""
   raise NotImplementedError(
       f'''{self.__class__} is an abstract class. Only classes inheriting this class can be called.'''     )






  @abstractmethod
  def   snake_case		(    self     ):







   """simple docstring"""
   raise NotImplementedError(
       f'''{self.__class__} is an abstract class. Only classes inheriting this class can be called.'''     )







  @abstractmethod
  def   snake_case		(    self			,  UpperCamelCase=False     ):







   """simple docstring"""
   raise NotImplementedError(
       f'''{self.__class__} is an abstract class. Only classes inheriting this class can be called.'''     )





class      snake_case    (    lowercase			):





  """simple docstring"""




  def __init__(    self			,  UpperCamelCase     ):







   """simple docstring"""
   super(UpperCamelCase			,  self     ).__init__()

   if not isinstance(UpperCamelCase			,  UpperCamelCase     ) or len(UpperCamelCase     ) == 0:
    raise ValueError(f'''`token_ids` has to be a non-empty list, but is {token_ids}.'''     )
   if any((not isinstance(UpperCamelCase			,  UpperCamelCase     ) or token_id < 0) for token_id in token_ids     ):
    raise ValueError(f'''Each list in `token_ids` has to be a list of positive integers, but is {token_ids}.'''     )

   lowerCamelCase_      =  token_ids

   lowerCamelCase_      =  len(self.token_ids     )
   lowerCamelCase_      =  -1  # the index of the currently fulfilled step
   lowerCamelCase_      =  False






  def   snake_case		(    self     ):







   """simple docstring"""
   if self.completed:
    return None
   return self.token_ids[self.fulfilled_idx + 1]






  def   snake_case		(    self			,  UpperCamelCase     ):







   """simple docstring"""
   if not isinstance(UpperCamelCase			,  UpperCamelCase     ):
    raise ValueError(f'''`token_id` has to be an `int`, but is {token_id} of type {type(UpperCamelCase     )}'''     )

   if self.completed:
    return False

   return token_id == self.token_ids[self.fulfilled_idx + 1]






  def   snake_case		(    self			,  UpperCamelCase     ):







   """simple docstring"""
   if not isinstance(UpperCamelCase			,  UpperCamelCase     ):
    raise ValueError(f'''`token_id` has to be an `int`, but is {token_id} of type {type(UpperCamelCase     )}'''     )

   lowerCamelCase_      =  False
   lowerCamelCase_      =  False
   lowerCamelCase_      =  False

   if self.does_advance(UpperCamelCase     ):
    self.fulfilled_idx += 1
    lowerCamelCase_      =  True
    if self.fulfilled_idx == (self.seqlen - 1):
     lowerCamelCase_      =  True
    lowerCamelCase_      =  completed
   else:
    # failed to make progress.
    lowerCamelCase_      =  True
    self.reset()
   return stepped, completed, reset






  def   snake_case		(    self     ):







   """simple docstring"""
   lowerCamelCase_      =  False
   lowerCamelCase_      =  0






  def   snake_case		(    self     ):







   """simple docstring"""
   return self.seqlen - (self.fulfilled_idx + 1)







  def   snake_case		(    self			,  UpperCamelCase=False     ):







   """simple docstring"""
   lowerCamelCase_      =  PhrasalConstraint(self.token_ids     )

   if stateful:
    lowerCamelCase_      =  self.seqlen
    lowerCamelCase_      =  self.fulfilled_idx
    lowerCamelCase_      =  self.completed

   return new_constraint





class      snake_case    :





  """simple docstring"""




  def __init__(    self			,  UpperCamelCase			,  UpperCamelCase=True     ):







   """simple docstring"""
   lowerCamelCase_      =  max([len(UpperCamelCase     ) for one in nested_token_ids]     )

   lowerCamelCase_      =  {}
   for token_ids in nested_token_ids:
    lowerCamelCase_      =  root
    for tidx, token_id in enumerate(UpperCamelCase     ):
     if token_id not in level:
      lowerCamelCase_      =  {}

     lowerCamelCase_      =  level[token_id]

   if no_subsets and self.has_subsets(UpperCamelCase			,  UpperCamelCase     ):
    raise ValueError(
        "Each list in `nested_token_ids` can't be a complete subset of another list, but is"
        f''' {nested_token_ids}.'''     )

   lowerCamelCase_      =  root






  def   snake_case		(    self			,  UpperCamelCase     ):







   """simple docstring"""
   lowerCamelCase_      =  self.trie

   for current_token in current_seq:
    lowerCamelCase_      =  start[current_token]

   lowerCamelCase_      =  list(start.keys()     )

   return next_tokens






  def   snake_case		(    self			,  UpperCamelCase     ):







   """simple docstring"""
   lowerCamelCase_      =  self.next_tokens(UpperCamelCase     )

   return len(UpperCamelCase     ) == 0






  def   snake_case		(    self			,  UpperCamelCase     ):







   """simple docstring"""
   lowerCamelCase_      =  list(root.values()     )
   if len(UpperCamelCase     ) == 0:
    return 1
   else:
    return sum([self.count_leaves(UpperCamelCase     ) for nn in next_nodes]     )







  def   snake_case		(    self			,  UpperCamelCase			,  UpperCamelCase     ):







   """simple docstring"""
   lowerCamelCase_      =  self.count_leaves(UpperCamelCase     )
   return len(UpperCamelCase     ) != leaf_count





class      snake_case    (    lowercase			):





  """simple docstring"""




  def __init__(    self			,  UpperCamelCase     ):







   """simple docstring"""
   super(UpperCamelCase			,  self     ).__init__()

   if not isinstance(UpperCamelCase			,  UpperCamelCase     ) or len(UpperCamelCase     ) == 0:
    raise ValueError(f'''`nested_token_ids` has to be a non-empty list, but is {nested_token_ids}.'''     )
   if any(not isinstance(UpperCamelCase			,  UpperCamelCase     ) for token_ids in nested_token_ids     ):
    raise ValueError(f'''`nested_token_ids` has to be a list of lists, but is {nested_token_ids}.'''     )
   if any(
       any((not isinstance(UpperCamelCase			,  UpperCamelCase     ) or token_id < 0) for token_id in token_ids     )
       for token_ids in nested_token_ids     ):
    raise ValueError(
        f'''Each list in `nested_token_ids` has to be a list of positive integers, but is {nested_token_ids}.'''     )

   lowerCamelCase_      =  DisjunctiveTrie(UpperCamelCase     )
   lowerCamelCase_      =  nested_token_ids

   lowerCamelCase_      =  self.trie.max_height
   lowerCamelCase_      =  []
   lowerCamelCase_      =  False






  def   snake_case		(    self     ):







   """simple docstring"""
   lowerCamelCase_      =  self.trie.next_tokens(self.current_seq     )

   if len(UpperCamelCase     ) == 0:
    return None
   else:
    return token_list






  def   snake_case		(    self			,  UpperCamelCase     ):







   """simple docstring"""
   if not isinstance(UpperCamelCase			,  UpperCamelCase     ):
    raise ValueError(f'''`token_id` is supposed to be type `int`, but is {token_id} of type {type(UpperCamelCase     )}'''     )

   lowerCamelCase_      =  self.trie.next_tokens(self.current_seq     )

   return token_id in next_tokens






  def   snake_case		(    self			,  UpperCamelCase     ):







   """simple docstring"""
   if not isinstance(UpperCamelCase			,  UpperCamelCase     ):
    raise ValueError(f'''`token_id` is supposed to be type `int`, but is {token_id} of type {type(UpperCamelCase     )}'''     )

   lowerCamelCase_      =  False
   lowerCamelCase_      =  False
   lowerCamelCase_      =  False

   if self.does_advance(UpperCamelCase     ):
    self.current_seq.append(UpperCamelCase     )
    lowerCamelCase_      =  True
   else:
    lowerCamelCase_      =  True
    self.reset()

   lowerCamelCase_      =  self.trie.reached_leaf(self.current_seq     )
   lowerCamelCase_      =  completed

   return stepped, completed, reset






  def   snake_case		(    self     ):







   """simple docstring"""
   lowerCamelCase_      =  False
   lowerCamelCase_      =  []






  def   snake_case		(    self     ):







   """simple docstring"""
   if self.completed:
    # since this can be completed without reaching max height
    return 0
   else:
    return self.seqlen - len(self.current_seq     )







  def   snake_case		(    self			,  UpperCamelCase=False     ):







   """simple docstring"""
   lowerCamelCase_      =  DisjunctiveConstraint(self.token_ids     )

   if stateful:
    lowerCamelCase_      =  self.seqlen
    lowerCamelCase_      =  self.current_seq
    lowerCamelCase_      =  self.completed

   return new_constraint





class      snake_case    :





  """simple docstring"""




  def __init__(    self			,  UpperCamelCase     ):







   """simple docstring"""
   lowerCamelCase_      =  constraints

   # max # of steps required to fulfill a given constraint
   lowerCamelCase_      =  max([c.seqlen for c in constraints]     )
   lowerCamelCase_      =  len(UpperCamelCase     )
   lowerCamelCase_      =  False

   self.init_state()






  def   snake_case		(    self     ):







   """simple docstring"""
   lowerCamelCase_      =  []
   lowerCamelCase_      =  None
   lowerCamelCase_      =  [constraint.copy(stateful=UpperCamelCase     ) for constraint in self.constraints]






  def   snake_case		(    self     ):







   """simple docstring"""
   lowerCamelCase_      =  0
   if self.inprogress_constraint:
    # extra points for having a constraint mid-fulfilled
    add += self.max_seqlen - self.inprogress_constraint.remaining()

   return (len(self.complete_constraints     ) * self.max_seqlen) + add






  def   snake_case		(    self     ):







   """simple docstring"""
   lowerCamelCase_      =  []
   if self.inprogress_constraint is None:
    for constraint in self.pending_constraints:  # "pending" == "unfulfilled yet"
     lowerCamelCase_      =  constraint.advance()
     if isinstance(UpperCamelCase			,  UpperCamelCase     ):
      token_list.append(UpperCamelCase     )
     elif isinstance(UpperCamelCase			,  UpperCamelCase     ):
      token_list.extend(UpperCamelCase     )
   else:
    lowerCamelCase_      =  self.inprogress_constraint.advance()
    if isinstance(UpperCamelCase			,  UpperCamelCase     ):
     token_list.append(UpperCamelCase     )
    elif isinstance(UpperCamelCase			,  UpperCamelCase     ):
     token_list.extend(UpperCamelCase     )

   if len(UpperCamelCase     ) == 0:
    return None
   else:
    return token_list






  def   snake_case		(    self			,  UpperCamelCase     ):







   """simple docstring"""
   self.init_state()

   if token_ids is not None:
    for token in token_ids:
     # completes or steps **one** constraint
     lowerCamelCase_ ,lowerCamelCase_      =  self.add(UpperCamelCase     )

     # the entire list of constraints are fulfilled
     if self.completed:
      break






  def   snake_case		(    self			,  UpperCamelCase     ):







   """simple docstring"""
   if not isinstance(UpperCamelCase			,  UpperCamelCase     ):
    raise ValueError(f'''`token_id` should be an `int`, but is `{token_id}`.'''     )

   lowerCamelCase_ ,lowerCamelCase_      =  False, False

   if self.completed:
    lowerCamelCase_      =  True
    lowerCamelCase_      =  False
    return complete, stepped

   if self.inprogress_constraint is not None:
    # In the middle of fulfilling a constraint. If the `token_id` *does* makes an incremental progress to current
    # job, simply update the state

    lowerCamelCase_ ,lowerCamelCase_ ,lowerCamelCase_      =  self.inprogress_constraint.update(UpperCamelCase     )
    if reset:
     # 1. If the next token breaks the progress, then we must restart.
     #     e.g. constraint = "I love pies" and sequence so far is "I love" but `token_id` == "books".

     #     But that doesn't mean we self.init_state(), since we only reset the state for this particular
     #     constraint, not the full list of constraints.

     self.pending_constraints.append(self.inprogress_constraint.copy(stateful=UpperCamelCase     )     )
     lowerCamelCase_      =  None

    if complete:
     # 2. If the next token completes the constraint, move it to completed list, set
     #     inprogress to None. If there are no pending constraints either, then this full list of constraints
     #     is complete.

     self.complete_constraints.append(self.inprogress_constraint     )
     lowerCamelCase_      =  None

     if len(self.pending_constraints     ) == 0:
      # we're done!
      lowerCamelCase_      =  True

   else:
    # Not in the middle of fulfilling a constraint. So does this `token_id` helps us step towards any of our list
    # of constraints?

    for cidx, pending_constraint in enumerate(self.pending_constraints     ):
     if pending_constraint.does_advance(UpperCamelCase     ):
      lowerCamelCase_ ,lowerCamelCase_ ,lowerCamelCase_      =  pending_constraint.update(UpperCamelCase     )

      if not stepped:
       raise Exception(
           "`constraint.update(token_id)` is not yielding incremental progress, "
           "even though `constraint.does_advance(token_id)` is true."     )

      if complete:
       self.complete_constraints.append(UpperCamelCase     )
       lowerCamelCase_      =  None

      if not complete and stepped:
       lowerCamelCase_      =  pending_constraint

      if complete or stepped:
       # If we made any progress at all, then it's at least not a "pending constraint".

       lowerCamelCase_      =  (
           self.pending_constraints[:cidx] + self.pending_constraints[cidx + 1 :]
       )

       if len(self.pending_constraints     ) == 0 and self.inprogress_constraint is None:
        # If there's no longer any pending after this and no inprogress either, then we must be
        # complete.

        lowerCamelCase_      =  True

       break  # prevent accidentally stepping through multiple constraints with just one token.

   return complete, stepped







  def   snake_case		(    self			,  UpperCamelCase=True     ):







   """simple docstring"""
   lowerCamelCase_      =  ConstraintListState(self.constraints     )  # we actually never though self.constraints objects
   # throughout this process. So it's at initialization state.

   if stateful:
    lowerCamelCase_      =  [
        constraint.copy(stateful=UpperCamelCase     ) for constraint in self.complete_constraints
    ]
    if self.inprogress_constraint is not None:
     lowerCamelCase_      =  self.inprogress_constraint.copy(stateful=UpperCamelCase     )
    lowerCamelCase_      =  [constraint.copy() for constraint in self.pending_constraints]

   return new_state







'''simple docstring'''

from __future__ import annotations

from fractions import Fraction





def __snake_case					(      UpperCAmelCase_						:						int					,				UpperCAmelCase_						:						int		):
 return (
     num != den and num % 10 == den // 10 and (num // 10) / (den % 10) == num / den
 )





def __snake_case					(      UpperCAmelCase_						:						int		):
 lowerCamelCase_      =  []
 lowerCamelCase_      =  11
 lowerCamelCase_      =  int("1" + "0" * digit_len		)
 for num in range(UpperCAmelCase_					,				UpperCAmelCase_		):
  while den <= 99:
   if (num != den) and (num % 10 == den // 10) and (den % 10 != 0):
    if is_digit_cancelling(UpperCAmelCase_					,				UpperCAmelCase_		):
     solutions.append(F'''{num}/{den}'''		)
   den += 1
  num += 1
  lowerCamelCase_      =  10
 return solutions





def __snake_case					(      UpperCAmelCase_						:						int = 2		):
 lowerCamelCase_      =  1.0
 for fraction in fraction_list(UpperCAmelCase_		):
  lowerCamelCase_      =  Fraction(UpperCAmelCase_		)
  result *= frac.denominator / frac.numerator
 return int(UpperCAmelCase_		)


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



