Interplanetary Mission

The National Space Center(NSC) is planning an interplanetary mission in a new galaxy far far away from earth. The galaxy has one star. There is a weird thing about that galaxy. It has an infinite number of planets. They form a straight line if you connect them to the star and every planet, along with the star, is exactly 2n distance away from each other, where n is an integer value. So the i th planet will be at i*2n distance from the star.

The NSC has somehow created a space station in the star. Astonishing, huh! Now they have built a space shuttle to travel to different planets.

The space shuttle is weird too. If the amount of fuel in the shuttle is x, then the shuttle travels exactly x3-x distance with that fuel. Unless you press the break, of course. But the engineers who made it forgot to put a break in the shuttle. Lazy Engineers!! So, the shuttle will only stop after finishing all the fuel.

A mission will be called successful only if the shuttle lands on a planet, not between two planets (starting from the space station). As the engineers are lazy, they have asked you to help them find the amount of fuel they need for a successful mission.

In short, given n and p, where p is the maximum fuel capacity, you have to find how many integer values of x between 1 and p can make their mission successful.

Input

Input starts with an integer T(0 < T < 105), denoting number of test cases.

The next T lines contains two integers each, n(0 <= n < 50 ), p(0 < p < 1018) described above.

Output

For each test case, print one line containing your answer to that test case.

Sample

1
3 10

5