






def  _a(  UpperCamelCase__				:						str							):




      '''simple docstring'''






      SCREAMING_SNAKE_CASE__     :				List[Any]									=0

      # if input_string is "aba" than new_input_string become "a|b|a"
      SCREAMING_SNAKE_CASE__     :				Optional[Any]									=''''''
      SCREAMING_SNAKE_CASE__     :				Dict									=''''''

      # append each character + "|" in new_string for range(0, length-1)
      for i in input_string[: len(UpperCamelCase__							) - 1]:
            new_input_string += i + "|"
      # append last character
      new_input_string += input_string[-1]

      # we will store the starting and ending of previous furthest ending palindromic
      # substring
      SCREAMING_SNAKE_CASE__     :				Optional[int]									=0, 0

      # length[i] shows the length of palindromic substring with center i
      SCREAMING_SNAKE_CASE__     :				Tuple									=[1 for i in range(len(UpperCamelCase__							)							)]

      # for each character in new_string find corresponding palindromic string
      SCREAMING_SNAKE_CASE__     :				Tuple									=0
      for j in range(len(UpperCamelCase__							)							):
            SCREAMING_SNAKE_CASE__     :				str									=1 if j > r else min(length[l + r - j] // 2,	r - j + 1							)
            while (
                j - k >= 0
                and j + k < len(UpperCamelCase__							)
                and new_input_string[k + j] == new_input_string[j - k]
            ):
                  k += 1

            SCREAMING_SNAKE_CASE__     :				Dict									=2 * k - 1

            # does this string is ending after the previously explored end (that is r) ?
            # if yes the update the new r to the last index of this
            if j + k - 1 > r:
                  SCREAMING_SNAKE_CASE__     :				Optional[int]									=j - k + 1  # noqa: E741
                  SCREAMING_SNAKE_CASE__     :				Union[str, Any]									=j + k - 1

            # update max_length and start position
            if max_length < length[j]:
                  SCREAMING_SNAKE_CASE__     :				Any									=length[j]
                  SCREAMING_SNAKE_CASE__     :				List[str]									=j

    # create that string
      SCREAMING_SNAKE_CASE__     :				List[Any]									=new_input_string[start - max_length // 2 : start + max_length // 2 + 1]
      for i in s:
            if i != "|":
                  output_string += i

      return output_string


if __name__ == "__main__":
  import doctest

  doctest.testmod()







'''simple docstring'''
from math import isqrt





def  _a(  UpperCamelCase__				:						int							):




      '''simple docstring'''






      SCREAMING_SNAKE_CASE__     :				int									=[True] * max_number
      for i in range(2,	isqrt(max_number - 1							) + 1							):
            if is_prime[i]:
                  for j in range(i**2,	UpperCamelCase__,	UpperCamelCase__							):
                        SCREAMING_SNAKE_CASE__     :				Any									=False

      return [i for i in range(2,	UpperCamelCase__							) if is_prime[i]]





def  _a(  UpperCamelCase__				:						int = 1_0**8							):




      '''simple docstring'''






      SCREAMING_SNAKE_CASE__     :				Tuple									=calculate_prime_numbers(max_number // 2							)

      SCREAMING_SNAKE_CASE__     :				int									=0
      SCREAMING_SNAKE_CASE__     :				int									=0
      SCREAMING_SNAKE_CASE__     :				Optional[int]									=len(UpperCamelCase__							) - 1
      while left <= right:
            while prime_numbers[left] * prime_numbers[right] >= max_number:
                  right -= 1
            semiprimes_count += right - left + 1
            left += 1

      return semiprimes_count


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