피보나치 수열 (f_n)은 다음과 같이 정의되는 수열이다.</p>

[f_n = \begin{cases} 0 & \text{if }n = 0 \ 1 & \text{if }n = 1 \ f_{n-1} + f_{n-2} & \text{if }n \ge 2 \end{cases}]

피보나미얼 (F_n) ((n) ≥ 1)은 (F_n = f_1 \times f_2 \times \dots \times f_n)으로 정의된다. 즉 (f_1, f_2, \dots, f_n)를 모두 곱한 값이다.

어떤 자연수 (k)에 대해, (F_n)을 (k)로 몇 번을 나누어야 (F_n)이 더 이상 (k)로 나누어 떨어지지 않는지를 구하는 프로그램을 작성하라.

입력 형식

첫 번째 줄에 두 자연수 n과 p (1 ≤ n ≤ 10⁹, 2 ≤ p ≤ 10³)이 공백을 사이로 두고 주어진다.

출력 형식

p - 1줄에 걸쳐 답을 출력한다. 이 중 i(1 ≤ i ≤ p - 1)번째 줄에는 F_n이 (i + 1)로 나누어 떨어지지 않도록 하기 위해 F_n을 (i + 1)로 나눠야 할 횟수를 출력해야 한다.

예제 입력

12 6

예제 출력

9
4
4
2
4

힌트

F₁₂ = 1,570,247,078,400 = 2⁹×3⁴×5²×...