





import torch
from torch import nn






class        snake_case_    (		nn.Module						):






  def __init__(							self			:					List[Any]       ,  _snake_case			:					int       ,  _snake_case			:					Dict       ,  _snake_case			:					Tuple       ,  _snake_case			:					Optional[Any]       ,  _snake_case			:					Any=1       ,  _snake_case			:					Union[str, Any]=False      )->List[Any]:






   '''simple docstring'''

   super().__init__()

   __lowerCAmelCase					:	List[str]      =       n_token
   __lowerCAmelCase					:	Any      =       d_embed
   __lowerCAmelCase					:	str      =       d_proj

   __lowerCAmelCase					:	Union[str, Any]      =       cutoffs + [n_token]
   __lowerCAmelCase					:	List[Any]      =       [0] + self.cutoffs
   __lowerCAmelCase					:	List[str]      =       div_val

   __lowerCAmelCase					:	Optional[Any]      =       self.cutoffs[0]
   __lowerCAmelCase					:	Union[str, Any]      =       len(self.cutoffs      ) - 1
   __lowerCAmelCase					:	int      =       self.shortlist_size + self.n_clusters

   if self.n_clusters > 0:
    __lowerCAmelCase					:	Any      =       nn.Parameter(torch.zeros(self.n_clusters       ,  self.d_embed      )      )
    __lowerCAmelCase					:	Optional[int]      =       nn.Parameter(torch.zeros(self.n_clusters      )      )

   __lowerCAmelCase					:	Any      =       nn.ModuleList()
   __lowerCAmelCase					:	List[str]      =       nn.ParameterList()

   if div_val == 1:
    for i in range(len(self.cutoffs      )      ):
     if d_proj != d_embed:
      self.out_projs.append(nn.Parameter(torch.FloatTensor(_snake_case       ,  _snake_case      )      )      )
     else:
      self.out_projs.append(_snake_case      )

    self.out_layers.append(nn.Linear(_snake_case       ,  _snake_case      )      )
   else:
    for i in range(len(self.cutoffs      )      ):
     __lowerCAmelCase ,					__lowerCAmelCase					:	Dict      =       self.cutoff_ends[i], self.cutoff_ends[i + 1]
     __lowerCAmelCase					:	int      =       d_embed // (div_val**i)

     self.out_projs.append(nn.Parameter(torch.FloatTensor(_snake_case       ,  _snake_case      )      )      )

     self.out_layers.append(nn.Linear(_snake_case       ,  r_idx - l_idx      )      )

   __lowerCAmelCase					:	Union[str, Any]      =       keep_order






  def 				UpperCAmelCase__						(							self			:					Tuple       ,  _snake_case			:					Tuple       ,  _snake_case			:					Tuple       ,  _snake_case			:					Tuple       ,  _snake_case			:					Optional[int]      )->int:






   '''simple docstring'''

   if proj is None:
    __lowerCAmelCase					:	Optional[int]      =       nn.functional.linear(_snake_case       ,  _snake_case       ,  bias=_snake_case      )
   else:
    # if CUDA_MAJOR <= 9 and CUDA_MINOR <= 1:
    __lowerCAmelCase					:	str      =       nn.functional.linear(_snake_case       ,  proj.t().contiguous()      )
    __lowerCAmelCase					:	Optional[int]      =       nn.functional.linear(_snake_case       ,  _snake_case       ,  bias=_snake_case      )
    # else:
    #     logit = torch.einsum('bd,de,ev->bv', (hidden, proj, weight.t()))
    #     if bias is not None:
    #         logit = logit + bias

   return logit






  def 				UpperCAmelCase__						(							self			:					List[str]       ,  _snake_case			:					Union[str, Any]       ,  _snake_case			:					Optional[int]=None       ,  _snake_case			:					List[str]=False      )->int:






   '''simple docstring'''

   if labels is not None:
    # Shift so that tokens < n predict n
    __lowerCAmelCase					:	List[Any]      =       hidden[..., :-1, :].contiguous()
    __lowerCAmelCase					:	Optional[Any]      =       labels[..., 1:].contiguous()
    __lowerCAmelCase					:	Optional[Any]      =       hidden.view(-1       ,  hidden.size(-1      )      )
    __lowerCAmelCase					:	Optional[int]      =       labels.view(-1      )
    if hidden.size(0      ) != labels.size(0      ):
     raise RuntimeError("""Input and labels should have the same size in the batch dimension."""      )
   else:
    __lowerCAmelCase					:	List[Any]      =       hidden.view(-1       ,  hidden.size(-1      )      )

   if self.n_clusters == 0:
    __lowerCAmelCase					:	str      =       self._compute_logit(_snake_case       ,  self.out_layers[0].weight       ,  self.out_layers[0].bias       ,  self.out_projs[0]      )
    if labels is not None:
     __lowerCAmelCase					:	int      =       labels != -100
     __lowerCAmelCase					:	Union[str, Any]      =       torch.zeros_like(_snake_case       ,  dtype=hidden.dtype       ,  device=hidden.device      )
     __lowerCAmelCase					:	Optional[int]      =       (
         -nn.functional.log_softmax(_snake_case       ,  dim=-1      )[mask].gather(1       ,  labels[mask].unsqueeze(1      )      ).squeeze(1      )
     )
    else:
     __lowerCAmelCase					:	int      =       nn.functional.log_softmax(_snake_case       ,  dim=-1      )
   else:
    # construct weights and biases
    __lowerCAmelCase ,					__lowerCAmelCase					:	List[Any]      =       [], []
    for i in range(len(self.cutoffs      )      ):
     if self.div_val == 1:
      __lowerCAmelCase ,					__lowerCAmelCase					:	Tuple      =       self.cutoff_ends[i], self.cutoff_ends[i + 1]
      __lowerCAmelCase					:	List[str]      =       self.out_layers[0].weight[l_idx:r_idx]
      __lowerCAmelCase					:	Optional[int]      =       self.out_layers[0].bias[l_idx:r_idx]
     else:
      __lowerCAmelCase					:	int      =       self.out_layers[i].weight
      __lowerCAmelCase					:	List[str]      =       self.out_layers[i].bias

     if i == 0:
      __lowerCAmelCase					:	int      =       torch.cat([weight_i, self.cluster_weight]       ,  dim=0      )
      __lowerCAmelCase					:	int      =       torch.cat([bias_i, self.cluster_bias]       ,  dim=0      )

     weights.append(_snake_case      )
     biases.append(_snake_case      )

    __lowerCAmelCase ,					__lowerCAmelCase ,					__lowerCAmelCase					:	List[Any]      =       weights[0], biases[0], self.out_projs[0]

    __lowerCAmelCase					:	Any      =       self._compute_logit(_snake_case       ,  _snake_case       ,  _snake_case       ,  _snake_case      )
    __lowerCAmelCase					:	Any      =       nn.functional.log_softmax(_snake_case       ,  dim=1      )

    if labels is None:
     __lowerCAmelCase					:	int      =       hidden.new_empty((head_logit.size(0      ), self.n_token)      )
    else:
     __lowerCAmelCase					:	Union[str, Any]      =       torch.zeros_like(_snake_case       ,  dtype=hidden.dtype       ,  device=hidden.device      )

    __lowerCAmelCase					:	Union[str, Any]      =       0
    __lowerCAmelCase					:	Tuple      =       [0] + self.cutoffs
    for i in range(len(_snake_case      ) - 1      ):
     __lowerCAmelCase ,					__lowerCAmelCase					:	Optional[Any]      =       cutoff_values[i], cutoff_values[i + 1]

     if labels is not None:
      __lowerCAmelCase					:	List[str]      =       (labels >= l_idx) & (labels < r_idx)
      __lowerCAmelCase					:	Union[str, Any]      =       mask_i.nonzero().squeeze()

      if indices_i.numel() == 0:
       continue

      __lowerCAmelCase					:	Union[str, Any]      =       labels.index_select(0       ,  _snake_case      ) - l_idx
      __lowerCAmelCase					:	Union[str, Any]      =       head_logprob.index_select(0       ,  _snake_case      )
      __lowerCAmelCase					:	Optional[int]      =       hidden.index_select(0       ,  _snake_case      )
     else:
      __lowerCAmelCase					:	str      =       hidden

     if i == 0:
      if labels is not None:
       __lowerCAmelCase					:	Union[str, Any]      =       head_logprob_i.gather(1       ,  target_i[:, None]      ).squeeze(1      )
      else:
       __lowerCAmelCase					:	Union[str, Any]      =       head_logprob[:, : self.cutoffs[0]]
     else:
      __lowerCAmelCase ,					__lowerCAmelCase ,					__lowerCAmelCase					:	Any      =       weights[i], biases[i], self.out_projs[i]

      __lowerCAmelCase					:	Any      =       self._compute_logit(_snake_case       ,  _snake_case       ,  _snake_case       ,  _snake_case      )
      __lowerCAmelCase					:	Optional[int]      =       nn.functional.log_softmax(_snake_case       ,  dim=1      )
      __lowerCAmelCase					:	Any      =       self.cutoffs[0] + i - 1  # No probability for the head cluster
      if labels is not None:
       __lowerCAmelCase					:	Union[str, Any]      =       head_logprob_i[:, cluster_prob_idx] + tail_logprob_i.gather(
           1       ,  target_i[:, None]      ).squeeze(1      )
      else:
       __lowerCAmelCase					:	Dict      =       head_logprob[:, cluster_prob_idx, None] + tail_logprob_i
       __lowerCAmelCase					:	str      =       logprob_i

     if labels is not None:
      if (hasattr(self       ,  """keep_order"""      ) and self.keep_order) or keep_order:
       out.index_copy_(0       ,  _snake_case       ,  -logprob_i      )
      else:
       out[offset : offset + logprob_i.size(0      )].copy_(-logprob_i      )
      offset += logprob_i.size(0      )

   return out






  def 				UpperCAmelCase__						(							self			:					Union[str, Any]       ,  _snake_case			:					str      )->Optional[Any]:






   '''simple docstring'''

   if self.n_clusters == 0:
    __lowerCAmelCase					:	List[str]      =       self._compute_logit(_snake_case       ,  self.out_layers[0].weight       ,  self.out_layers[0].bias       ,  self.out_projs[0]      )
    return nn.functional.log_softmax(_snake_case       ,  dim=-1      )
   else:
    # construct weights and biases
    __lowerCAmelCase ,					__lowerCAmelCase					:	List[str]      =       [], []
    for i in range(len(self.cutoffs      )      ):
     if self.div_val == 1:
      __lowerCAmelCase ,					__lowerCAmelCase					:	Union[str, Any]      =       self.cutoff_ends[i], self.cutoff_ends[i + 1]
      __lowerCAmelCase					:	Optional[Any]      =       self.out_layers[0].weight[l_idx:r_idx]
      __lowerCAmelCase					:	int      =       self.out_layers[0].bias[l_idx:r_idx]
     else:
      __lowerCAmelCase					:	int      =       self.out_layers[i].weight
      __lowerCAmelCase					:	Optional[Any]      =       self.out_layers[i].bias

     if i == 0:
      __lowerCAmelCase					:	Optional[int]      =       torch.cat([weight_i, self.cluster_weight]       ,  dim=0      )
      __lowerCAmelCase					:	Union[str, Any]      =       torch.cat([bias_i, self.cluster_bias]       ,  dim=0      )

     weights.append(_snake_case      )
     biases.append(_snake_case      )

    __lowerCAmelCase ,					__lowerCAmelCase ,					__lowerCAmelCase					:	List[Any]      =       weights[0], biases[0], self.out_projs[0]
    __lowerCAmelCase					:	str      =       self._compute_logit(_snake_case       ,  _snake_case       ,  _snake_case       ,  _snake_case      )

    __lowerCAmelCase					:	Optional[Any]      =       hidden.new_empty((head_logit.size(0      ), self.n_token)      )
    __lowerCAmelCase					:	List[str]      =       nn.functional.log_softmax(_snake_case       ,  dim=1      )

    __lowerCAmelCase					:	Tuple      =       [0] + self.cutoffs
    for i in range(len(_snake_case      ) - 1      ):
     __lowerCAmelCase ,					__lowerCAmelCase					:	Dict      =       cutoff_values[i], cutoff_values[i + 1]

     if i == 0:
      __lowerCAmelCase					:	Optional[Any]      =       head_logprob[:, : self.cutoffs[0]]
     else:
      __lowerCAmelCase ,					__lowerCAmelCase ,					__lowerCAmelCase					:	Tuple      =       weights[i], biases[i], self.out_projs[i]

      __lowerCAmelCase					:	List[Any]      =       self._compute_logit(_snake_case       ,  _snake_case       ,  _snake_case       ,  _snake_case      )
      __lowerCAmelCase					:	Tuple      =       nn.functional.log_softmax(_snake_case       ,  dim=1      )

      __lowerCAmelCase					:	Union[str, Any]      =       head_logprob[:, -i] + tail_logprob_i
      __lowerCAmelCase					:	Tuple      =       logprob_i

    return out






from math import isqrt






def 	_SCREAMING_SNAKE_CASE		(      SCREAMING_SNAKE_CASE		:int   )      ->   list[int]:
 __lowerCAmelCase					:	Tuple      =       [True] * max_number
 for i in range(2   ,   isqrt(max_number - 1   ) + 1   ):
  if is_prime[i]:
   for j in range(i**2   ,   SCREAMING_SNAKE_CASE   ,   SCREAMING_SNAKE_CASE   ):
    __lowerCAmelCase					:	Tuple      =       False

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






def 	_SCREAMING_SNAKE_CASE		(      SCREAMING_SNAKE_CASE		:int = 10**8   )      ->   int:
 __lowerCAmelCase					:	int      =       calculate_prime_numbers(max_number // 2   )

 __lowerCAmelCase					:	List[Any]      =       0
 __lowerCAmelCase					:	List[str]      =       0
 __lowerCAmelCase					:	List[Any]      =       len(SCREAMING_SNAKE_CASE   ) - 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() = }''')