Special Christmas Tree

Time limit3sMemory limit256 MB

Summary

Find the maximum node count of a binary tree with exactly L leaves and height at most H.

Level: Medium6 of 10
Topics: Math, Greedy, Tree
Solved: No attempts yet

Problem

Christmas is coming, everyone is building a Christmas tree, and you are no exception. You want yours to be special, so you decided to build a binary tree and hang its root from the ceiling.

In this problem a binary tree is a collection of connected nodes. The topmost node is the root. Every node has 0, 1, or 2 nodes hanging from it, called its children. A node with no children is a leaf. Every node except the root has exactly one parent.

You bought a decoration pack and you want to use all of its items to decorate all the leaves of the tree. The height of your room limits the tree, so the tree cannot be longer than the room. The height of a tree is the number of edges on the path from the root to the farthest leaf.

Each leaf must be decorated by exactly one item, each item decorates exactly one leaf, and you must use every item.

Find the most special tree. Tree X is more special than tree Y if X has more nodes than Y.

Input

The first line contains a single integer $T$ ( $1 \le T \le 10\,000$ ), the number of test cases. Each of the next $T$ lines contains two integers $H$ and $L$ separated by a single space ( $0 \le H \le 10^9$ , $1 \le L \le 10^9$ , $L \le 2^H$ ), the maximum possible height of the tree and the number of its leaves.

Output

For each test case, print one line of the form Case n: x, where $n$ is the number of the test case starting from 1 and $x$ is the number of nodes of the most special Christmas tree that has exactly $L$ leaves and height at most $H$ .

Examples3

Example 1
Input
```
2
3 2
3 3
```
Expected output
```
Case 1: 7
Case 2: 9
```
Example 2
Input
```
1
0 1
```
Expected output
```
Case 1: 1
```

Example 3

Input

Expected output

Case 1: 3
Case 2: 7
Case 3: 15
Case 4: 2047