Vaqt limiti: 1 sekund
Xotira limiti: 64 MB
A
group of pirates is travelling 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 ﬁrst), 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 ﬁrst line of the input
contains a single number: the number of test cases to follow. Each test case
has the following format:
• One line
with two integers n and k, where 1 ≤ n ≤ 15 and n ≤ k ≤
40. The ﬁrst 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 in the
input, the output should contain one integer 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.
№ |
Example input |
Example output |
1 |
3 1 3 3 4 3 16 |
1 1 5 |