output_description: Print N lines. In i-th line print the answer to the question when k = i.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      x_1 y_1
      x_2 y_2
      :
      x_N y_N
attempt: import sys
  
  readline = sys.stdin.readline
  
  
  def gcd(a, b):
      while b:
          a, b = b, a % b
      return a
  
  
  def egcd(a, b):
      if a == 0:
          return b, 0, 1
      else:
          g, y, x = egcd(b % a, a)
          return g, x - (b // a) * y, y
  
  
  N = int(readline())
  res = []
  for i in range(1, N):
      if i * i > 8 * N:
          break
      if (8 * N) % i:
          continue
      res.append(i)
      res.append(8 * N // i)
  
  
  def sqrt(x):
      ok = 0
      ng = 10**18
      while (ng - ok) > 1:
          med = (ok + ng) // 2
          if med * med <= x:
              ok = med
          else:
              ng = med
      return ok
  
  
  M = 8 * N
  
  ans = 2 * N
  for r in res:
      if r == 1:
          continue
      u = M // r
      if u == 1 or u == 2:
          continue
      if gcd(r, u) > 2:
          continue
      gc, xx, yy = egcd(r, u)
      if gc == 1:
          xx *= 2
          yy *= 2
      xx *= -1
      yy *= -1
      xx %= u
      k = xx * r
      Ml = k * (k + 2)
      j = (sqrt(1 + Ml) - 1) // 2
      ans = min(ans, j)
  print(ans)
  
problem_description: Statement
  
  There are N cities on a 2D plane. The coordinate of the i-th city is (x_i,
  y_i). Here (x_1, x_2, \dots, x_N) and (y_1, y_2, \dots, y_N) are both
  permuations of (1, 2, \dots, N).
  
  For each k = 1,2,\dots,N, find the answer to the following question:
  
  Rng is in City k. Rng can perform the following move arbitrarily many times:
  
    * move to another city that has a smaller x-coordinate and a smaller y-coordinate, or a larger x-coordinate and a larger y-coordinate, than the city he is currently in.
  
  How many cities (including City k) are reachable from City k?
samples: [{"input": "4\n    1 4\n    2 3\n    3 1\n    4 2", "output": "1\n    1\n    2\n    2\n    \n\nRng can reach City 4 from City 3, or conversely City 3 from City 4.\n\n* * *"}, {"input": "7\n    6 4\n    4 3\n    3 5\n    7 1\n    2 7\n    5 2\n    1 6", "output": "3\n    3\n    1\n    1\n    2\n    3\n    2"}]