Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
115 - The 12th Zhejiang University Programming Contest - I
Game

Time Limit: 3 Seconds      Memory Limit: 65536 KB

Alice and Bod decide to play a new stone game. At the beginning Alice puts n(n>1) stones (out of N in all) on the table. Alice and Bob remove the stones in turn. At each step the player should remove some number of stones. The number of stones the player removed should be at least one, and cannot exceed m times of the number of stones the player removed at the last step. The player who removes the last stone wins the game. Alice always plays first and of course at the first turn, she cannot remove all the stones. Alice wants to know how many positive integers n she can choose to win the game if both players play optimally.

Since you're an ace programmer, Alice wants you to help her.

Input

There are multiple test cases. The first line of input contains an integer T (0 < T ≤ 500) indicating the number of test cases. Then T test cases follow.

Each test case is a line of 2 integers m and N(0 < m ≤ 2012, 1 < N < 231)

Output

For each test case output the number of positive integers Alice can choose for n to make her win the game.

Sample Input

3
1 10
2 10
3 10

Sample Output

6
5
4

Author: CAO, Peng
Submit    Status