반란 진압

시간 제한1초메모리 제한128 MB

요약

n척의 배에 k명의 해적을 나눠 각 배에 충성 해적을 최소 한 명씩 두고, 각 배의 충성 해적 수가 자기 배와 양옆 배의 불충 해적 수 이상이 되게 하면서 불충 해적 수를 최대로 만든다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 완전 탐색, 그리디
정답자: 아직 제출이 없습니다

문제

해적 무리가 한 줄로 늘어선 배들의 선단을 이루어 항해하고 있다. 선장이 통제력을 잃어 가면서, 일부 해적은 불충하며 반란을 일으킬 준비가 되어 있다.

반란은 다음 규칙으로 일어난다. 임의의 배 $S$ 를 생각하자. 배 $S$ 를 덮칠 수 있는 불충한 해적은 $S$ 자신에 탄 불충한 해적, $S$ 의 바로 앞 배(존재한다면)에 탄 불충한 해적, 그리고 $S$ 의 바로 뒤 배(존재한다면)에 탄 불충한 해적이다. 만약 $S$ 에 탄 충성스러운 해적의 수가 이렇게 모인 불충한 해적의 수보다 적으면(엄격히 작으면), 그 불충한 해적들이 $S$ 로 노를 저어 와 배를 빼앗는다.

반란을 막기 위해 선장은 어떤 배도 빼앗기지 않도록 모든 해적을 배들에 배치하려고 한다. 단, 배를 운항하려면 모든 배에는 충성스러운 해적이 적어도 한 명 있어야 한다.

배의 수 $n$ 과 해적의 총수 $k$ 가 주어질 때, 어떤 배도 빼앗기지 않도록 배치할 수 있는 불충한 해적의 최대 수를 구하여라.

입력

첫 줄에 테스트 케이스의 수를 나타내는 정수 하나가 주어진다.

각 테스트 케이스는 두 정수 $n$ 과 $k$ 가 주어지는 한 줄로 이루어진다 ( $1 \le n \le 15$ , $n \le k \le 40$ ). $n$ 은 배의 수, $k$ 는 선단에 있는 (충성스럽든 불충하든) 해적의 총수이다.

출력

각 테스트 케이스마다, 어떤 배도 빼앗기지 않도록 배치할 수 있는 불충한 해적의 최대 수를 정수 하나로 한 줄에 출력한다.

예제2

예제 1
입력
```
3
1 3
3 4
3 16
```
예상 출력
```
1
1
5
```
예제 2
입력
```
1
1 2
```
예상 출력
```
1
```