Pavers

In the land of Quendor, walkways and hallways are always $2$mb wide. An mb is a mini bloit, about $1/2000$ of a bloit. J. Pierpont Flathead hired the Frobozz Magic Paver Company to lay new walkways at every one of his banks, and he wants to pick the patterns himself. There are so many walkways that Frobozz decided to first write a program that counts every way to cover one walkway completely.

Three kinds of pavers are available.

• a square paver $1$mb on a side
• a $2$mb by $1$mb rectangular paver, usable in both orientations
• a right tromino, the L shaped paver, usable in all four orientations

A paver may not stick out past the walkway and two pavers may not overlap, and every cell of the walkway must be covered by exactly one paver. Two coverings count as different if any paver sits in a different place.

For example, a $2 \times 1$ walkway has $2$ coverings, and adding up the pavers used in both of them gives $2$ square pavers of size $1 \times 1$ and $1$ rectangular paver of size $2 \times 1$.

A $2 \times 2$ walkway has $11$ coverings, and adding up the pavers used in all eleven gives $16$ square pavers, $8$ rectangular pavers and $4$ trominoes.

You are given the length $n$ of a walkway that is $2$mb tall and $n$mb long. Write a program that reports how many coverings it has and how many pavers of each kind those coverings use in total. Each per kind count is summed over all coverings, not over a single one.

The first line contains the number of data sets $P$. ($1 \le P \le 10\,000$)

Each of the next $P$ lines holds one data set. A line contains the data set number $K$ and the walkway length $n$, separated by a single space. ($1 \le K \le 10\,000$, $1 \le n \le 14$)

The data sets are independent and are all processed the same way. The upper bound on $n$ is chosen so that all five output values fit in an unsigned $32$ bit integer.

For each data set, print one line with five integers separated by a single space: the data set number $K$, the number of coverings of the $2 \times n$ walkway, the total number of $1 \times 1$ square pavers used by those coverings, the total number of $2 \times 1$ rectangular pavers and the total number of trominoes.