Apartment Residents

Interview

Time limit0.5sMemory limit128 MB

Summary

Compute the resident count in room n on floor k, defined by repeated prefix sums starting from room i having i residents on floor 0.

Level: Easy3 of 10
Topics: Dynamic programming, Math, Recursion
Solved: No attempts yet

Problem

An apartment starts at floor 0, and every floor has rooms numbered from 1. On floor 0, room i has exactly i residents.

For floors 1 and above, the number of residents in room b on floor a is the sum of the residents in rooms 1 through b on the floor directly below, floor (a - 1).

Given several queries k and n, find how many residents live in room n on floor k when every room follows this rule.

Input

The first line contains the number of test cases, T. For each test case, an integer k and an integer n are given on separate lines.

Output

For each test case, print the number of residents in room n on floor k, one answer per line.

Constraints

1 ≤ k ≤ 14
1 ≤ n ≤ 14

Examples1

Example 1
Input
```
2
1
3
2
3
```
Expected output
```
6
10
```