C. Cuckoo Synchronization
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Artem is excited to be visiting his grandma for the weekend since he is able to play around with her vast collection of $$$N$$$ cuckoo clocks. Artem has put a lot of effort on synchronizing the clocks so that all of them emit their first cuckoo at minute $$$1$$$. But having such a variety of clocks comes with a problem: each clock will repeat their sounds at different intervals.

To be more specific, the $$$i-$$$th ($$$1 \leq i \leq N$$$) cuckoo clock will make a sound every $$$i$$$ minutes after their synchronized sound. For example, for $$$N \geq 3$$$ the $$$i=3$$$ clock will keep emitting sounds every $$$3$$$ minutes after it's first cuckoo at time $$$1$$$. So Artem will be able to listen to it's beautiful sound on the $$$1, 4, 7, 10, \dots$$$ minutes.

Excited for all of his hard work, Artem wants to show the experiment to his grandma. Currently it's time $$$0$$$ and he knows that his grandma will be back from the store in $$$T$$$ minutes. Artem wants you to help him figure out how many clocks will make their cuckoo sound exactly when his grandma arrives!

Input

The first line contains an integer $$$Q (1 \leq Q \leq 100)$$$ — the number of test cases.

For each test case, the only line contains two integers — $$$N (1 \leq N \leq 10^{9})$$$ and $$$T (1 \leq T \leq 10^9)$$$, for the number of cuckoo clocks and the time in minutes when Artem's grandma is back, respectively.

Output

For each test case, output the number of clocks that make the cuckoo sound at exactly $$$T$$$ minutes.

Examples
Input
5
5 1
10 5
10 6
5 3
6 11
Output
5
3
2
2
3
Input
3
1000 647
1000000 123456
1000000000 1000000000
Output
8
4
20