






'''simple docstring'''






from collections import deque




def 							_SCREAMING_SNAKE_CASE	(					A	:							Union[str, Any]	)     ->			str:







   """simple docstring"""
   return input(A	).strip().split(' '	)




def 							_SCREAMING_SNAKE_CASE	(					A	:							int	,		A	:							int	)     ->			dict[int, list[int]]:







   """simple docstring"""
   __snake_case					:   dict[int, list[int]]  				=			{}
   for i in range(A	):
      __snake_case					:   Dict  				=			[]

   for e in range(A	):
      __snake_case				,__snake_case					:   Dict  				=			(int(A	) for i in _input(F"""Edge {e + 1}: <node1> <node2> """	))
      graph[x].append(A	)
   return graph




def 							_SCREAMING_SNAKE_CASE	(					A	:							int	,		A	:							int	)     ->			dict[int, list[int]]:







   """simple docstring"""
   __snake_case					:   dict[int, list[int]]  				=			{}
   for i in range(A	):
      __snake_case					:   List[str]  				=			[]

   for e in range(A	):
      __snake_case				,__snake_case					:   List[Any]  				=			(int(A	) for i in _input(F"""Edge {e + 1}: <node1> <node2> """	))
      graph[x].append(A	)
      graph[y].append(A	)
   return graph




def 							_SCREAMING_SNAKE_CASE	(					A	:							int	,		A	:							int	)     ->			dict[int, list[tuple[int, int]]]:







   """simple docstring"""
   __snake_case					:   dict[int, list[tuple[int, int]]]  				=			{}
   for i in range(A	):
      __snake_case					:   Union[str, Any]  				=			[]

   for e in range(A	):
      __snake_case				,__snake_case				,__snake_case					:   Any  				=			(int(A	) for i in _input(F"""Edge {e + 1}: <node1> <node2> <weight> """	))
      graph[x].append((y, w)	)
      graph[y].append((x, w)	)
   return graph


if __name__ == "__main__":
      __A						, __A     						= (int(i) for i in _input('''Number of nodes and edges: '''))

      __A     						= int(
          _input(
              '''Press 1 or 2 or 3 \n'''
              '''1. Unweighted directed \n'''
              '''2. Unweighted undirected \n'''
              '''3. Weighted undirected \n'''
          )[0]
      )

      __A     						= {
          1: initialize_unweighted_directed_graph,
          2: initialize_unweighted_undirected_graph,
          3: initialize_weighted_undirected_graph,
      }[graph_choice](n, m)




def 							_SCREAMING_SNAKE_CASE	(					A	:							int	,		A	:							Any	)     ->			int:







   """simple docstring"""
   __snake_case				,__snake_case					:   Union[str, Any]  				=			{s}, [s]
   print(A	)
   while _s:
      __snake_case					:   Tuple  				=			0
      for i in g[_s[-1]]:
         if i not in vis:
            _s.append(A	)
            vis.add(A	)
            __snake_case					:   Optional[Any]  				=			1
            print(A	)
            break
      if not flag:
         _s.pop()




def 							_SCREAMING_SNAKE_CASE	(					A	:							Dict	,		A	:							List[Any]	)     ->			Any:







   """simple docstring"""
   __snake_case				,__snake_case					:   Union[str, Any]  				=			{s}, deque([s]	)
   print(A	)
   while q:
      __snake_case					:   str  				=			q.popleft()
      for v in g[u]:
         if v not in vis:
            vis.add(A	)
            q.append(A	)
            print(A	)




def 							_SCREAMING_SNAKE_CASE	(					A	:							Tuple	,		A	:							Tuple	)     ->			int:







   """simple docstring"""
   __snake_case				,__snake_case				,__snake_case					:   str  				=			{s: 0}, set(), {s: 0}
   while True:
      if len(A	) == len(A	) - 1:
         break
      __snake_case					:   Dict  				=			10_00_00
      for i in dist:
         if i not in known and dist[i] < mini:
            __snake_case					:   Dict  				=			dist[i]
            __snake_case					:   Optional[int]  				=			i
      known.add(A	)
      for v in g[u]:
         if v[0] not in known and dist[u] + v[1] < dist.get(v[0]	,		10_00_00	):
            __snake_case					:   str  				=			dist[u] + v[1]
            __snake_case					:   int  				=			u
   for i in dist:
      if i != s:
         print(dist[i]	)




def 							_SCREAMING_SNAKE_CASE	(					A	:							Union[str, Any]	,		A	:							List[Any]=None	,		A	:							int=None	)     ->			Any:







   """simple docstring"""
   if q is None:
      __snake_case					:   int  				=			[1]
   if ind is None:
      __snake_case					:   List[Any]  				=			[0] * (len(A	) + 1)  # SInce oth Index is ignored
      for u in g:
         for v in g[u]:
            ind[v] += 1
      __snake_case					:   Union[str, Any]  				=			deque()
      for i in g:
         if ind[i] == 0:
            q.append(A	)
   if len(A	) == 0:
      return
   __snake_case					:   Optional[int]  				=			q.popleft()
   print(A	)
   for w in g[v]:
      ind[w] -= 1
      if ind[w] == 0:
         q.append(A	)
   topo(A	,		A	,		A	)




def 							_SCREAMING_SNAKE_CASE	(					)     ->			Any:







   """simple docstring"""
   __snake_case					:   Union[str, Any]  				=			input().strip()
   __snake_case					:   List[Any]  				=			[]
   for _ in range(A	):
      a.append(map(A	,		input().strip().split()	)	)
   return a, n




def 							_SCREAMING_SNAKE_CASE	(					A	:							Tuple	)     ->			int:







   """simple docstring"""
   ((__snake_case)				,(__snake_case))					:   Any  				=			a_and_n
   __snake_case					:   List[Any]  				=			list(A	)
   __snake_case					:   Union[str, Any]  				=			[[0] * n for i in range(A	)]
   for k in range(A	):
      for i in range(A	):
         for j in range(A	):
            if dist[i][j] > dist[i][k] + dist[k][j]:
               __snake_case					:   List[Any]  				=			dist[i][k] + dist[k][j]
               __snake_case					:   Optional[int]  				=			k
   print(A	)




def 							_SCREAMING_SNAKE_CASE	(					A	:							List[Any]	,		A	:							Union[str, Any]	)     ->			str:







   """simple docstring"""
   __snake_case				,__snake_case				,__snake_case					:   Optional[Any]  				=			{s: 0}, set(), {s: 0}
   while True:
      if len(A	) == len(A	) - 1:
         break
      __snake_case					:   Tuple  				=			10_00_00
      for i in dist:
         if i not in known and dist[i] < mini:
            __snake_case					:   Tuple  				=			dist[i]
            __snake_case					:   Optional[Any]  				=			i
      known.add(A	)
      for v in g[u]:
         if v[0] not in known and v[1] < dist.get(v[0]	,		10_00_00	):
            __snake_case					:   str  				=			v[1]
            __snake_case					:   Union[str, Any]  				=			u
   return dist




def 							_SCREAMING_SNAKE_CASE	(					)     ->			str:







   """simple docstring"""
   __snake_case				,__snake_case					:   Optional[int]  				=			map(A	,		input().split(' '	)	)
   __snake_case					:   str  				=			[]
   for _ in range(A	):
      edges.append(map(A	,		input().split(' '	)	)	)
   return edges, n




def 							_SCREAMING_SNAKE_CASE	(					A	:							Union[str, Any]	)     ->			Dict:







   """simple docstring"""
   # Sort edges on the basis of distance
   ((__snake_case)				,(__snake_case))					:   List[str]  				=			e_and_n
   e.sort(reverse=A	,		key=lambda A	: x[2]	)
   __snake_case					:   List[Any]  				=			[{i} for i in range(1	,		n + 1	)]
   while True:
      if len(A	) == 1:
         break
      print(A	)
      __snake_case					:   Tuple  				=			e.pop()
      for i in range(len(A	)	):
         if x[0] in s[i]:
            break
      for j in range(len(A	)	):
         if x[1] in s[j]:
            if i == j:
               break
            s[j].update(s[i]	)
            s.pop(A	)
            break





def 							_SCREAMING_SNAKE_CASE	(					A	:							Optional[int]	)     ->			Dict:







   """simple docstring"""
   __snake_case					:   str  				=			[]
   for node in graph:
      if not graph[node]:
         isolated.append(A	)
   return isolated







'''simple docstring'''






from math import gcd




def 							_SCREAMING_SNAKE_CASE	(					A	:							int = 1_20_00	)     ->			int:







   """simple docstring"""
   __snake_case					:   Dict  				=			0
   for d in range(max_d + 1	):
      for n in range(d // 3 + 1	,		(d + 1) // 2	):
         if gcd(A	,		A	) == 1:
            fractions_number += 1
   return fractions_number


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