Stifling the Mutiny

Time limit1sMemory limit128 MB

Summary

Distribute k pirates over n ships, each with at least one loyal pirate, so that no ship's loyal count is below the disloyal pirates on it and its neighbors, maximizing disloyal pirates.

Level: Medium6 of 10
Topics: Dynamic programming, Brute force, Greedy
Solved: No attempts yet

Problem

A band of pirates sails in a convoy of ships arranged in a single row. As the captain loses control, some pirates turn disloyal and are ready to mutiny.

A mutiny works as follows. Consider any ship $S$ . The disloyal pirates that can reach $S$ are those aboard $S$ itself, those aboard the ship immediately before $S$ (if $S$ is not the first), and those aboard the ship immediately after $S$ (if $S$ is not the last). If the number of loyal pirates aboard $S$ is strictly less than this combined number of reachable disloyal pirates, those disloyal pirates row over to $S$ and capture it.

To prevent any mutiny, the captain distributes all pirates across the ships so that no ship can be captured. Every ship must carry at least one loyal pirate in order to operate.

Given the number of ships $n$ and the total number of pirates $k$ , determine the maximum number of disloyal pirates that can be distributed so that no ship can be captured.

Input

The first line contains a single integer: the number of test cases.

Each test case is one line with two integers $n$ and $k$ ( $1 \le n \le 15$ , $n \le k \le 40$ ): $n$ is the number of ships and $k$ is the total number of pirates (loyal and disloyal) in the convoy.

Output

For each test case, output a single line with one integer: the maximum number of disloyal pirates that can be distributed so that no ship can be captured.

Examples2

Example 1
Input
```
3
1 3
3 4
3 16
```
Expected output
```
1
1
5
```
Example 2
Input
```
1
1 2
```
Expected output
```
1
```