#
# By https://oeis.org/wiki/User:Hiroaki_Yamanouchi August 16 2015.
# (communicated via Antti Karttunen)
#
# To compute quickly sequence https://oeis.org/A219661
#

def solve(N):
  def sum_of_digits_in_factorial_expansion(n):
    ret = 0
    assert(n < facts[N + 2])
    for i in range(N + 1, 0, -1):
      if n >= facts[i]:
        ret += n // facts[i]
        n %= facts[i]
    return ret

  facts = [1]
  for i in range(1, 2 * N + 4):
    facts.append(facts[i-1] * i)

  DIGIT_SUM_MAX = N * (N + 1) // 2

  pre = 0
  while facts[pre] <= DIGIT_SUM_MAX:
    pre += 1

  pre_total = facts[pre]
  tmp1 = [[0] * pre_total for _ in range(DIGIT_SUM_MAX + 1)]
  tmp2 = [[0] * pre_total for _ in range(DIGIT_SUM_MAX + 1)]

  for i in range(DIGIT_SUM_MAX + 1):
    for j in range(0, pre_total):
      k = j - i - sum_of_digits_in_factorial_expansion(j)
      if j == k:
        tmp1[i][j] = 0
        tmp2[i][j] = j
      elif k < 0:
        tmp1[i][j] = 1
        tmp2[i][j] = k
      else:
        tmp1[i][j] = 1 + tmp1[i][k]
        tmp2[i][j] = tmp2[i][k]

  dp1, dp2 = tmp1, tmp2

  for d in range(pre, N + 1):
    ndp1 = [[-1] * pre_total for _ in range(DIGIT_SUM_MAX + 1)]
    ndp2 = [[-1] * pre_total for _ in range(DIGIT_SUM_MAX + 1)]
    for z in range(0,  DIGIT_SUM_MAX - d * (d - 1) // 2 + 1):
      for l in range(-pre_total, 0):
        idx = l
        step = 0
        for i in range(d + 1):
          step += dp1[z + d - i][idx]
          idx   = dp2[z + d - i][idx]
          if idx == 0:
            break
        ndp1[z][l] = step
        ndp2[z][l] = idx
    dp1, dp2 = ndp1, ndp2

  return dp1[0][-1]

def main():
  T = 20
  seq = []

  for n in range(1, T + 1):
    seq.append(solve(n))

  for i in range(T - 1, 0, -1):
    seq[i] -= seq[i-1]

  for i in range(T):
    print("%d %d" % (i + 1, seq[i]))
  print("")

if __name__ == "__main__":
  main()