U385049 斐波那契数列

斐波那契数列 $\lbrace F_n \rbrace$ 是一种经典的数列，数列的前两项都是 $1$，即 $F_1 = F_2 = 1$。 从第三项开始，数列的每一项都等于前两项之和，即 $F_n = F_{n-2} + F_{n-1}$。

给定两个正整数 $n$ 和 $k$，请问：斐波那契数列的第 $1$ 项到第 $n$ 项中（包括第 $1$ 项和第 $n$ 项），有多少项不是 $k$ 的倍数？

输入共两行： 第一行输入一个正整数，表示 $n$； 第二行输入一个正整数，表示 $k$。

输出一个非负整数，表示答案。

通过五组测试数据即可获得 $100$ 分。 ### 样例解释 斐波那契数列的前 $10$ 项依次为 $1$、$1$、$2$、$3$、$5$、$8$、$13$、$21$、$34$、$55$，有 $7$ 项不是 $2$ 的倍数。 ### 测试数据说明 本题共有六组测试数据： * 对于第一组测试数据，满足 $n < 10$，$k = 2$； * 对于前三组测试数据，满足 $n < 10$，$k < 5$； * 对于前五组测试数据，满足 $n < 10^4$，$k < 10$； * 对于所有的测试数据，满足 $n < 10^{30}$，$k < 5000$。