小华非常喜欢数字，尤其喜欢‘1’，现在他想知道1~n（十进制）在k进制下共有多少个‘1’？（例如k=2时，3包含两个1，所以n=3时，1~3中共有4个‘1’）
输入包含多组数据，每组数据一行，包含两个整数n和k（1<=n<=1000000，2<=k<=16）。
数据组数小于105
输出1~n在k进制下包含‘1’的个数
3 2 7 2 10 3
4 12 9