Hongjun and balanced tables

Time limit2sMemory limit512 MB

Summary

Count the ways to fill a 3-by-C grid with nonnegative integers so that every triple of cells satisfying a + c = 2b sums to S.

Level: Medium6 of 10
Topics: Combinatorics, Math, Dynamic programming, Implementation
Solved: No attempts yet

Problem

You are given an empty table with 3 rows and $C$ columns, together with an integer $S$ . Hongjun writes one nonnegative integer in every cell of the table.

Take three cells, one from each of the three rows. If the center of one of them is the midpoint of the segment joining the centers of the other two, the three cells are called balanced. If the three cells lie in column $a$ of row 1, column $b$ of row 2, and column $c$ of row 3, this condition is the same as $a + c = 2b$ . The picture below shows one balanced set of three cells when $C = 8$ .

Three balanced cells in a table with 3 rows and 8 columns

Hongjun wants to fill the table so that for every balanced set of three cells, the numbers written in those three cells add up to $S$ . For two tables $A$ and $B$ , let $A(i, j)$ and $B(i, j)$ be the numbers written in row $i$ and column $j$ . The two tables are different if $A(i, j) \neq B(i, j)$ for at least one pair $i$ , $j$ . Given $C$ and $S$ , write a program that counts the tables Hongjun can write.

Input

The first line contains the number of test cases $T$ ( $1 \le T \le 100$ ).

Each of the next $T$ lines contains $C$ and $S$ ( $1 \le C \le 50$ , $0 \le S \le 50$ ), separated by a space.

Output

For each test case, print the number of possible tables on its own line.

Examples2

Example 1
Input
```
2
3 1
4 3
```
Expected output
```
5
34
```
Example 2
Input
```
3
1 0
1 5
2 4
```
Expected output
```
1
21
225
```