赢了这局我就睡觉

题目描述

王木木总是失眠，因为他总是立一些奇怪的flag，比如给我幽鬼，不赢砍手；比如赢一把就睡觉，so...

王木木赢一局游戏的概率为p，一天晚上最多玩n局，当王木木某一局游戏结束时，他的胜率大于p，他就去睡觉，不然就继续玩。

如果某天打完n局，王木木的胜率还没有超过p，那么王木木会愤怒地把游戏删掉，求一个游戏能在王木木的硬盘中存活的天数的数学期望。

输入

第一行是数据组数N.

接着是N组数据. 每一组数据是一个分数p和一个整数n

1 ≤ N ≤ 3000, 0 ≤ p < 1, p的分母不会超过1000 1 ≤ n ≤ 100.

输出

对于每组数据，输出一行，为期望值，保留为整数

输入样例

4
1/2 1
1/2 2
0/1 10
1/2 3

输出样例

2
2
1
2