## IPSC 2007

## Problem D – Delicious Cake

Lenka likes to bake cakes since her childhood, when she has learned to bake from
her mom. She soon became a cake expert able to bake chocolate cakes, apple
pies, muffins, cookies, cheese cakes, tortes and many other cakes.

Recently, she has started her studies of math at Comenius University in
Bratislava. In the first year she is taking combinatorics class. Today she is
studying for the final exam. Since the brain needs a lot of sugar to study math,
she has baked, just for herself, her favorite, very delicious, strawberry cake.

The cake, still hot, is lying on an **N**×**M** inch sheet pan.
Hungrily waiting for the cake to cool off Lenka came up with an interesting combinatorial question:
How many different possibilities to cut the cake are there so that every
connected piece consists of some number of 1×1 inch unit squares?

### Problem specification

The cake can be viewed as a grid consisting of **N**×**M** unit squares.
We are allowed to cut the cake along the grid lines. As a result the cake splits into
several connected pieces. (Two unit squares remain connected
if they share a side which was not cut.) How many different ways are there to cut the cake?
We consider two cuttings of the cake to be the same if the resulting connected pieces
of both cuttings have the same shape and are at the same positions within the cake.
In other words, we are only counting those cuttings where no cut leads between two
unit squares that are in the same connected piece.

The following picture ilustrates all the 12 different possible ways how to cut a 2×2 inch cake:

Note that cutting, for example, as on following picture

is the same as not cutting at all.

### Input specification

The first line of the input file contains an integer **T**
specifying the number of test cases.
Each test case is preceded by a blank line.

Each test case consists of a single line with two positive integers **N** and **M** – dimensions of the cake.

### Output specification

For each test case output a line with a single positive integer – the number of
different possibilities how to cut the cake.

### Example

**Input:**
2
1 2
2 2

**Output:**
2
12

**Credits:**

**Problemsetter(s):** Yulka

**Contest-related materials:** Misof, Tom, David