


def 					lowerCamelCase_   (	_a     ,       _a	):




  """simple docstring"""






  lowerCAmelCase__       :      int   					= len(__a	) + 1
  lowerCAmelCase__       :      List[str]   					= len(__a	) + 1

  # dp is a 2d matrix where dp[i][j] denotes whether prefix string of
  # length i of input_string matches with prefix string of length j of
  # given pattern.
  # "dp" stands for dynamic programming.
  lowerCAmelCase__       :      Optional[int]   					= [[0 for i in range(__a	)] for j in range(__a	)]

  # since string of zero length match pattern of zero length
  lowerCAmelCase__       :      str   					= 1

  # since pattern of zero length will never match with string of non-zero length
  for i in range(1     ,       __a	):
    lowerCAmelCase__       :      Optional[Any]   					= 0

  # since string of zero length will match with pattern where there
  # is at least one * alternatively
  for j in range(1     ,       __a	):
    lowerCAmelCase__       :      Dict   					= dp[0][j - 2] if pattern[j - 1] == '*' else 0

  # now using bottom-up approach to find for all remaining lengths
  for i in range(1     ,       __a	):
    for j in range(1     ,       __a	):
      if input_string[i - 1] == pattern[j - 1] or pattern[j - 1] == ".":
        lowerCAmelCase__       :      Tuple   					= dp[i - 1][j - 1]

      elif pattern[j - 1] == "*":
        if dp[i][j - 2] == 1:
          lowerCAmelCase__       :      List[str]   					= 1
        elif pattern[j - 2] in (input_string[i - 1], "."):
          lowerCAmelCase__       :      int   					= dp[i - 1][j]
        else:
          lowerCAmelCase__       :      Any   					= 0
      else:
        lowerCAmelCase__       :      Optional[Any]   					= 0

  return bool(dp[-1][-1]	)


if __name__ == "__main__":
  import doctest

  doctest.testmod()
  # inputing the strings
  # input_string = input("input a string :")
  # pattern = input("input a pattern :")

  lowerCamelCase						=		'''aab'''
  lowerCamelCase						=		'''c*a*b'''

  # using function to check whether given string matches the given pattern
  if match_pattern(input_string, pattern):
    print(f'''{input_string} matches the given pattern {pattern}''')
  else:
    print(f'''{input_string} does not match with the given pattern {pattern}''')








from math import isqrt






def 					lowerCamelCase_   (	_a	):




		"""simple docstring"""






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

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






def 					lowerCamelCase_   (	_a = 10**8	):




		"""simple docstring"""






		lowerCAmelCase__       :      Any   					= calculate_prime_numbers(max_number // 2	)

		lowerCAmelCase__       :      Tuple   					= 0
		lowerCAmelCase__       :      List[Any]   					= 0
		lowerCAmelCase__       :      Optional[int]   					= len(_a	) - 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() = }''')




