Hozirda online


Masalalar soni: 909

Foydalanuvchilar soni: 8820

Jo'natishlar soni: 714406

Muhokama yozuvlari: 4541

Yangiliklar soni: 97

Yangiliklar izohlari: 1174

So'ngi izohlar

187. Stifling the Mutiny
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 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 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 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 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

3 4

3 16





Mening urinishlarim(0) Muhokama (0) Jo'natish Eng yaxshi yechimlar Barcha muvaffaqiyatli urinishlar(6) Barcha urinishlar(24)