output_description: Print the number of choices of K in which N becomes 1 in the end.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
attempt: import numpy as np
  
  N, M = map(int, input().split())
  ABC = np.zeros((N, 3))
  for i in range(N):
      ABC[i][0], ABC[i][1], ABC[i][2] = map(int, input().split())
  DEF = np.zeros((M, 3))
  for i in range(M):
      DEF[i][0], DEF[i][1], DEF[i][2] = map(int, input().split())
  
  # 座標圧縮
  x_co = {-(10**9) - 1, 10**9 + 1}
  y_co = {-(10**9) - 1, 10**9 + 1}
  for i in range(N):
      x_co.add(ABC[i][0])
      x_co.add(ABC[i][1])
      y_co.add(ABC[i][2])
  for i in range(M):
      x_co.add(DEF[i][0])
      y_co.add(DEF[i][1])
      y_co.add(DEF[i][2])
  
  x_co = np.array(sorted(list(x_co)))
  y_co = np.array(sorted(list(y_co)))
  xL = len(x_co) - 1
  yL = len(y_co) - 1
  x_co_d = {x_co[i]: i for i in range(xL + 1)}
  y_co_d = {y_co[i]: i for i in range(yL + 1)}
  
  # 柵の存在
  s_ex_tate = np.zeros((yL + 1, xL))
  s_ex_yoko = np.zeros((xL + 1, yL))
  for i in range(N):
      a = x_co_d[ABC[i][0]]
      b = x_co_d[ABC[i][1]]
      c = y_co_d[ABC[i][2]]
      s_ex_tate[c][a:b] = 1
  for i in range(M):
      d = x_co_d[DEF[i][0]]
      e = y_co_d[DEF[i][1]]
      f = y_co_d[DEF[i][2]]
      s_ex_yoko[d][e:f] = 1
  
  # 初期位置
  for i in range(xL):
      if x_co[i + 1] > 0:
          xf = [i]
          break
      if x_co[i + 1] == 0:
          xf = [i, i + 1]
          break
  for i in range(yL):
      if y_co[i + 1] > 0:
          yf = [i]
          break
      if y_co[i + 1] == 0:
          yf = [i, i + 1]
          break
  
  
  def sq(x, y):
      return int((x_co[x + 1] - x_co[x]) * (y_co[y + 1] - y_co[y]))
  
  
  # 探索
  Q = []
  # houmon = [[False] * yL for _ in range(xL)]
  houmon = np.zeros((xL, yL))
  ans = 0
  is_inf = False
  for x in xf:
      for y in yf:
          houmon[x][y] = 1
          Q.append((x, y))
  
  while Q:
      x, y = Q.pop()
      if x in [0, xL - 1] or y in [0, yL - 1]:
          is_inf = True
          break
      ans += sq(x, y)
      if (not houmon[x - 1][y]) and (not s_ex_yoko[x][y]):
          houmon[x - 1][y] = True
          Q.append((x - 1, y))
      if (not houmon[x][y - 1]) and (not s_ex_tate[y][x]):
          houmon[x][y - 1] = True
          Q.append((x, y - 1))
      if (not houmon[x + 1][y]) and (not s_ex_yoko[x + 1][y]):
          houmon[x + 1][y] = True
          Q.append((x + 1, y))
      if (not houmon[x][y + 1]) and (not s_ex_tate[y + 1][x]):
          houmon[x][y + 1] = True
          Q.append((x, y + 1))
  
  if is_inf:
      print("INF")
  else:
      print(ans)
  
problem_description: Statement
  
  Given is a positive integer N.
  
  We will choose an integer K between 2 and N (inclusive), then we will repeat
  the operation below until N becomes less than K.
  
    * Operation: if K divides N, replace N with N/K; otherwise, replace N with N-K.
  
  In how many choices of K will N become 1 in the end?
samples: [{"input": "6", "output": "3\n    \n\nThere are three choices of K in which N becomes 1 in the end: 2, 5, and 6.\n\nIn each of these choices, N will change as follows:\n\n  * When K=2: 6 \\to 3 \\to 1\n  * When K=5: 6 \\to 1\n  * When K=6: 6 \\to 1\n\n* * *"}, {"input": "3141", "output": "13\n    \n\n* * *"}, {"input": "314159265358", "output": "9"}]