Problem 1039. -- 勇士的挑战

1039: 勇士的挑战

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 22  Solved: 5
[Submit][Status][Web Board]

Description

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

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

Input

第一行一个整数T,表示有T组测试数据,接下来T行,每行一组测试数据,为两个整数m,n(0<m<10^100,n是质数,而且1<n<100)

Output

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

Sample Input

1
30 2

Sample Output

0

HINT

Source

[Submit][Status]