def  __UpperCamelCase    (						A ,							A = False							):
     if n == 2:
          return True
     if not n % 2 or n < 2:
          return False
     if n > 5 and n % 10 not in (1, 3, 7, 9):  # can quickly check last digit
          return False
     if n > 3317044064679887385961981 and not allow_probable:
          raise ValueError(
              '''Warning: upper bound of deterministic test is exceeded. '''
              '''Pass allow_probable=True to allow probabilistic test. '''
              '''A return value of True indicates a probable prime.'''							)
     # array bounds provided by analysis
     UpperCamelCase__										=      [
         2047,
         1373653,
         25326001,
         3215031751,
         2152302898747,
         3474749660383,
         341550071728321,
         1,
         3825123056546413051,
         1,
         1,
         318665857834031151167461,
         3317044064679887385961981,
     ]

     UpperCamelCase__										=      [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
     for idx, _p in enumerate(A ,							1							):
          if n < _p:
               # then we have our last prime to check
               UpperCamelCase__										=      primes[:idx]
               break
     UpperCamelCase__						,       UpperCamelCase__										=      n - 1, 0
     # break up n -1 into a power of 2 (s) and
     # remaining odd component
     # essentially, solve for d * 2 ** s == n - 1
     while d % 2 == 0:
          d //= 2
          s += 1
     for prime in plist:
          UpperCamelCase__										=      False
          for r in range(A							):
               UpperCamelCase__										=      pow(A ,							d * 2**r ,							A							)
               # see article for analysis explanation for m
               if (r == 0 and m == 1) or ((m + 1) % n == 0):
                    UpperCamelCase__										=      True
                    # this loop will not determine compositeness
                    break
          if pr:
               continue
          # if pr is False, then the above loop never evaluated to true,
          # and the n MUST be composite
          return False
     return True







def  __UpperCamelCase    (						):
     assert not miller_rabin(561							)
     assert miller_rabin(563							)
     # 2047

     assert not miller_rabin(838201							)
     assert miller_rabin(838207							)
     # 1_373_653

     assert not miller_rabin(17316001							)
     assert miller_rabin(17316017							)
     # 25_326_001

     assert not miller_rabin(3078386641							)
     assert miller_rabin(3078386653							)
     # 3_215_031_751

     assert not miller_rabin(1713045574801							)
     assert miller_rabin(1713045574819							)
     # 2_152_302_898_747

     assert not miller_rabin(2779799728307							)
     assert miller_rabin(2779799728327							)
     # 3_474_749_660_383

     assert not miller_rabin(113850023909441							)
     assert miller_rabin(113850023909527							)
     # 341_550_071_728_321

     assert not miller_rabin(1275041018848804351							)
     assert miller_rabin(1275041018848804391							)
     # 3_825_123_056_546_413_051

     assert not miller_rabin(79666464458507787791867							)
     assert miller_rabin(79666464458507787791951							)
     # 318_665_857_834_031_151_167_461

     assert not miller_rabin(552840677446647897660333							)
     assert miller_rabin(552840677446647897660359							)
     # 3_317_044_064_679_887_385_961_981
     # upper limit for probabilistic test


if __name__ == "__main__":
     test_miller_rabin()




import os
from typing import Optional

import fsspec
from fsspec.archive import AbstractArchiveFileSystem
from fsspec.utils import DEFAULT_BLOCK_SIZE



class     _A   (    __UpperCamelCase							):
  SCREAMING_SNAKE_CASE_	:	List[str]						=""
  SCREAMING_SNAKE_CASE_	:	str						=(
      None  # protocol passed in prefix to the url. ex: "gzip", for gzip://file.txt::http://foo.bar/file.txt.gz
  )
  SCREAMING_SNAKE_CASE_	:	str						=None  # compression type in fsspec. ex: "gzip"
  SCREAMING_SNAKE_CASE_	:	str						=None  # extension of the filename to strip. ex: "".gz" to get file.txt from file.txt.gz






  def __init__(self   ,				SCREAMING_SNAKE_CASE_ = ""   ,				SCREAMING_SNAKE_CASE_ = None   ,				SCREAMING_SNAKE_CASE_ = None   ,				**SCREAMING_SNAKE_CASE_	)		->      List[str]:





       '''simple docstring'''





       super().__init__(self   ,				**SCREAMING_SNAKE_CASE_	)
       # always open as "rb" since fsspec can then use the TextIOWrapper to make it work for "r" mode
       UpperCamelCase__										=      fsspec.open(
           SCREAMING_SNAKE_CASE_   ,				mode='''rb'''   ,				protocol=SCREAMING_SNAKE_CASE_   ,				compression=self.compression   ,				client_kwargs={
               '''requote_redirect_url''': False,  # see https://github.com/huggingface/datasets/pull/5459
               '''trust_env''': True,  # Enable reading proxy env variables.
               **(target_options or {}).pop('''client_kwargs'''   ,				{}	),  # To avoid issues if it was already passed.
           }   ,				**(target_options or {})   ,				)
       UpperCamelCase__										=      os.path.basename(self.file.path.split('''::'''	)[0]	)
       UpperCamelCase__										=      (
           self.compressed_name[: self.compressed_name.rindex('''.'''	)]
           if '''.''' in self.compressed_name
           else self.compressed_name
       )
       UpperCamelCase__										=      None






  @classmethod
  def 		_a					(cls   ,				SCREAMING_SNAKE_CASE_	)		->      Optional[Any]:





       '''simple docstring'''





       return super()._strip_protocol(SCREAMING_SNAKE_CASE_	).lstrip('''/'''	)






  def 		_a					(self	)		->      Union[str, Any]:





       '''simple docstring'''





       if self.dir_cache is None:
            UpperCamelCase__										=      {**self.file.fs.info(self.file.path	), '''name''': self.uncompressed_name}
            UpperCamelCase__										=      {f['''name''']: f}






  def 		_a					(self   ,				SCREAMING_SNAKE_CASE_	)		->      List[Any]:





       '''simple docstring'''





       return self.file.open().read()






  def 		_a					(self   ,				SCREAMING_SNAKE_CASE_   ,				SCREAMING_SNAKE_CASE_ = "rb"   ,				SCREAMING_SNAKE_CASE_=None   ,				SCREAMING_SNAKE_CASE_=True   ,				SCREAMING_SNAKE_CASE_=None   ,				**SCREAMING_SNAKE_CASE_   ,				)		->      List[Any]:





       '''simple docstring'''





       UpperCamelCase__										=      self._strip_protocol(SCREAMING_SNAKE_CASE_	)
       if mode != "rb":
            raise ValueError(F"Tried to read with mode {mode} on file {self.file.path} opened with mode 'rb'"	)
       return self.file.open()



class     _A   (    __UpperCamelCase							):
  SCREAMING_SNAKE_CASE_	:	Tuple						="bz2"
  SCREAMING_SNAKE_CASE_	:	List[str]						="bz2"
  SCREAMING_SNAKE_CASE_	:	List[Any]						=".bz2"



class     _A   (    __UpperCamelCase							):
  SCREAMING_SNAKE_CASE_	:	Tuple						="gzip"
  SCREAMING_SNAKE_CASE_	:	Dict						="gzip"
  SCREAMING_SNAKE_CASE_	:	List[Any]						=".gz"



class     _A   (    __UpperCamelCase							):
  SCREAMING_SNAKE_CASE_	:	List[Any]						="lz4"
  SCREAMING_SNAKE_CASE_	:	str						="lz4"
  SCREAMING_SNAKE_CASE_	:	Any						=".lz4"



class     _A   (    __UpperCamelCase							):
  SCREAMING_SNAKE_CASE_	:	Dict						="xz"
  SCREAMING_SNAKE_CASE_	:	List[str]						="xz"
  SCREAMING_SNAKE_CASE_	:	Optional[int]						=".xz"



class     _A   (    __UpperCamelCase							):
  SCREAMING_SNAKE_CASE_	:	Optional[Any]						="zstd"
  SCREAMING_SNAKE_CASE_	:	Optional[int]						="zstd"
  SCREAMING_SNAKE_CASE_	:	Optional[int]						=".zst"






  def __init__(self   ,				SCREAMING_SNAKE_CASE_   ,				SCREAMING_SNAKE_CASE_ = "rb"   ,				SCREAMING_SNAKE_CASE_ = None   ,				SCREAMING_SNAKE_CASE_ = None   ,				SCREAMING_SNAKE_CASE_ = DEFAULT_BLOCK_SIZE   ,				**SCREAMING_SNAKE_CASE_   ,				)		->      List[Any]:





       '''simple docstring'''





       super().__init__(
           fo=SCREAMING_SNAKE_CASE_   ,				mode=SCREAMING_SNAKE_CASE_   ,				target_protocol=SCREAMING_SNAKE_CASE_   ,				target_options=SCREAMING_SNAKE_CASE_   ,				block_size=SCREAMING_SNAKE_CASE_   ,				**SCREAMING_SNAKE_CASE_   ,				)
       # We need to wrap the zstd decompressor to avoid this error in fsspec==2021.7.0 and zstandard==0.15.2:
       #
       # File "/Users/user/.virtualenvs/hf-datasets/lib/python3.7/site-packages/fsspec/core.py", line 145, in open
       #     out.close = close
       # AttributeError: 'zstd.ZstdDecompressionReader' object attribute 'close' is read-only
       #
       # see https://github.com/intake/filesystem_spec/issues/725
       UpperCamelCase__										=      self.file.__enter__



       class     _A   :






         def __init__(self   ,				SCREAMING_SNAKE_CASE_	)		->      int:





              '''simple docstring'''





              UpperCamelCase__										=      file_






         def __enter__(self	)		->      Union[str, Any]:





              '''simple docstring'''





              self._file.__enter__()
              return self






         def __exit__(self   ,				*SCREAMING_SNAKE_CASE_   ,				**SCREAMING_SNAKE_CASE_	)		->      List[Any]:





              '''simple docstring'''





              self._file.__exit__(*SCREAMING_SNAKE_CASE_   ,				**SCREAMING_SNAKE_CASE_	)






         def __iter__(self	)		->      Dict:





              '''simple docstring'''





              return iter(self._file	)






         def 		_a					(self	)		->      Dict:





              '''simple docstring'''





              return next(self._file	)






         def __getattr__(self   ,				SCREAMING_SNAKE_CASE_	)		->      str:





              '''simple docstring'''





              return getattr(self._file   ,				SCREAMING_SNAKE_CASE_	)

       def fixed_enter(*SCREAMING_SNAKE_CASE_   ,				**SCREAMING_SNAKE_CASE_	):
            return WrappedFile(_enter(*SCREAMING_SNAKE_CASE_   ,				**SCREAMING_SNAKE_CASE_	)	)

       UpperCamelCase__										=      fixed_enter



