피보나미얼

피보나치 수열 $f_n$은 다음과 같이 정의한다.

$f_0 = 0, \quad f_1 = 1, \quad f_n = f_{n-1} + f_{n-2} \;\; (n \ge 2)$

피보나미얼 $F_n$ ($n \ge 1$)은 $F_n = f_1 \times f_2 \times \cdots \times f_n$으로 정의한다. 즉 $f_1$부터 $f_n$까지를 모두 곱한 값이다.

$2$ 이상 $p$ 이하인 각 자연수 $k$에 대해, $F_n$이 더 이상 $k$로 나누어떨어지지 않을 때까지 $F_n$을 $k$로 몇 번 나눠야 하는지 구하는 프로그램을 작성하라.

첫째 줄에 자연수 $n$과 $p$가 공백 하나를 사이에 두고 주어진다. ($1 \le n \le 10^9$, $2 \le p \le 10^3$)

$p - 1$개의 줄에 답을 출력한다. $i$번째 줄 ($1 \le i \le p - 1$)에는 $F_n$이 더 이상 $i + 1$로 나누어떨어지지 않게 하려면 $F_n$을 $i + 1$로 몇 번 나눠야 하는지 출력한다.

$F_{12} = 1570247078400 = 2^9 \times 3^4 \times 5^2 \times 7 \times 11 \times 13 \times 17 \times 89$이므로, $F_{12}$는 $2$로 아홉 번, $4$로 네 번 나눌 수 있다.