定义 $S_p(n)$ 表示 $n$ 在 $p$ 进制下各个数位的和。

现在给定 $n,p$，求有多少整数 $k\in[0,n]$ 满足 $S_p(k)+S_p(n-k)\ge p-1+S_p(n)$。

$n\le 10^{18},p\le 10^5$，$p$ 是素数，多组测试 $t\le 10^5$。

Input:

2
2 2
7 7

Output:

1
6