#OJ1452. em 8 又见博弈

em 8 又见博弈

em 8 又见博弈

Time Limit: 1 Sec  Memory Limit: 128 MB

Description

A和B打算玩一个石子游戏。在刚开始A拿n(n>1)个石子放在桌子上。A和B轮流取石子。每次最少取1个,并且不能比上一次取的多m倍。获得最后一个石子的人获胜。现在他们决定A先取,但是先取的人不能拿走所有的石子。求A要想获胜第一步有多少种取法。

Input

第一行输入一个数T代表测试数据个数(T<=50)。接下来T行每行1个数代表m,n。(0<m<=2012,1<n<2^32) 

Output

对于每个测试数据输出A想获胜取法的个数。每行输出一个结果。

Sample Input

3
1 10
2 10
3 10

Sample Output

6
5
4

HINT

Append Code

Source