A group of pirates is traveling in a convoy of ships, sailing in a row. However, the pirate captain is starting to lose control, and some disloyal pirates are ready to mute. As soon as on any ship S, the number of loyal pirates on S is outnumbered by the combined number of disloyal pirates on S, the previous ship (if S is not the first), and the next ship (if S is not the last) in the convoy, the disloyal pirates on these ships will row to S and take it over. To prevent an outbreak of mutiny, the captain decides to distribute the loyal and disloyal pirates over the ships in such a way that the disloyal pirates cannot capture any ship. Of course, each ship must have at least one loyal pirate to operate the ship.

Input

The first line contains the number of test cases. Each test is one line that contains two integers n and k (1 ≤ n ≤ 15, n ≤ k ≤ 40). The first number is the number of ships; the second number is the total number of pirates (whether loyal or disloyal) in the convoy.

Output

For every test case print on a single line the maximum number of disloyal pirates that the captain can distribute over the ships such that the disloyal pirates cannot capture any ship.