输入描述:

输入包含多组数据，每组数据一行，包含两个整数n和k（1<=n<=1000000，2<=k<=N）。

输出描述:

输出1~n在k进制下包含‘1’的个数。