1. import time
  3. #start_time = time.time()
  4. #def TIME_(): print(time.time()-start_time)
  6. import os, sys
  7. from io import BytesIO, IOBase
  8. from types import GeneratorType
  9. from bisect import bisect_left, bisect_right
  10. from collections import defaultdict as dd, deque as dq, Counter as dc
  11. import math, string, heapq as h
  12. BUFSIZE = 8192
  14. class FastIO(IOBase):
  15. newlines = 0
  16. def __init__(self, file):
  17. import os
  18. self.os = os
  19. self._fd = file.fileno()
  20. self.buffer = BytesIO()
  21. self.writable = "x" in file.mode or "r" not in file.mode
  22. self.write = self.buffer.write if self.writable else None
  23. def read(self):
  24. while True:
  25. b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
  26. if not b:
  27. break
  28. ptr = self.buffer.tell()
  29. self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
  30. self.newlines = 0
  31. return self.buffer.read()
  32. def readline(self):
  33. while self.newlines == 0:
  34. b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
  35. self.newlines = b.count(b"\n") + (not b)
  36. ptr = self.buffer.tell()
  37. self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
  38. self.newlines -= 1
  39. return self.buffer.readline()
  40. def flush(self):
  41. if self.writable:
  42. self.os.write(self._fd, self.buffer.getvalue())
  43. self.buffer.truncate(0), self.buffer.seek(0)
  45. class IOWrapper(IOBase):
  46. def __init__(self, file):
  47. self.buffer = FastIO(file)
  48. self.flush = self.buffer.flush
  49. self.writable = self.buffer.writable
  50. self.write = lambda s: self.buffer.write(s.encode("ascii"))
  51. self.read = lambda: self.buffer.read().decode("ascii")
  52. self.readline = lambda: self.buffer.readline().decode("ascii")
  54. sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
  55. input = lambda: sys.stdin.readline().rstrip("\r\n")
  57. def getInt(): return int(input())
  58. def getStrs(): return input().split()
  59. def getInts(): return list(map(int,input().split()))
  60. def getStr(): return input()
  61. def listStr(): return list(input())
  62. def getMat(n): return [getInts() for _ in range(n)]
  63. def getBin(): return list(map(int,list(input())))
  64. def isInt(s): return '0' <= s[0] <= '9'
  65. def ceil_(a,b): return (a+b-1)//b
  67. MOD = 10**9 + 7
  69. """
  71. """
  72. from random import randint as ri
  74. LIM = 10**6+1
  75. facs = [[] for _ in range(LIM+1)]
  77. def primes(n):
  78. for i in range(2,n):
  79. if not min_div[i]:
  80. for j in range(i,n,i):
  81. min_div[j] = i
  82. return
  84. min_div = [0]*(LIM+1)
  85. min_div[1] = 1
  86. primes(LIM+1)
  87. facs[1] = [1]
  89. for i in range(2,LIM+1):
  90. facs[i] = [1]
  91. j = i
  92. while j > 1:
  93. x = min_div[j]
  94. c = 1
  95. j //= x
  96. while min_div[j] == x:
  97. c += 1
  98. j //= x
  99. new = []
  100. curr = 1
  101. for cc in range(1,c+1):
  102. curr *= x
  103. for k in facs[i]:
  104. new.append(k*curr)
  105. facs[i] += new
  106. facs[i].sort()
  108. def solve2(tot,min_):
  109. if tot % min_: return None
  110. if not tot: return 0
  111. if tot == min_: return 0
  112. best = 0
  113. for x in facs[tot]:
  114. if x > max(2,min_) and x % min_ == 0:
  115. y = solve2(tot-x,x)
  116. if y is not None:
  117. best = max(best,y)
  118. #print(tot,min_,best)
  119. return 1 + best
  121. def solve(case):
  122. N = getInt()
  123. ans = solve2(N,1)
  124. print("Case #{}: {}".format(case,ans))
  125. #print("Case #{}: {}".format(case,' '.join(list(map(str,ans)))))
  126. return
  128. T = getInt()
  129. for _ in range(T):
  130. solve(_+1)
  131. #solve()
  133. #TIME_()