问题描述

为了打败威胁世界的冥王哈帝斯，咕噜姐少男来到了叹息之墙，发现了众黄金圣斗士为了发出太阳的光辉，集合了所有的黄金圣衣，人马座艾奥罗斯取出弓箭射向了叹息之墙，但叹息之墙与传说中的不同，依然没有一线裂痕。

正当众人绝望之时，咕噜姐少男发现墙上出现了一些文字：“如果哈帝斯有 $m$ 个冥斗士，圣斗士一次使出绝技可以消灭 $n$ 个冥斗士，而且圣斗士每一次绝技只消灭 $n$ 个冥斗士，当哈帝斯的冥斗士小于 $n$ 时，圣斗士将不屑于消灭这些冥斗士，而将这些冥斗士留给咕噜姐少男，最后咕噜姐少男需要消灭多少个冥斗士？”显然圣斗士的数学不太好，于是众圣斗士转向咕噜姐少男求助，咕噜姐少男数学和计算机都很强，但是下到冥界时忘记带笔记本电脑了，于是咕噜姐少男打电话找到你，希望你能帮助他们冲过最后的叹息之墙。前进吧！勇者！冲过叹息之墙！

输入格式

第一行一个整数 $T$，表示有 $T$ 组测试数据。接下来 $T$ 行，每行一组测试数据，为两个整数 $m$，$n$（$0 < m < 10^{100}$，$n$ 是质数，而且 $1 < n < 100$）。

输出格式

共 $T$ 行，每行一个整数 $k$，表示咕噜姐少男需要消灭的冥斗士的个数。

样例输入

1
30 2

样例输出

0