Sphere Online Judge



SPOJ Problem Set (classical)

2159. Delicious Cake

Problem code: CAKE3

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 NM 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 11 inch unit squares?

Problem specification

The cake can be viewed as a grid consisting of NM 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 22 inch cake: 12 possible ways of cutting a 22 cake
Note that cutting, for example, as on following picture
Not a good way of cutting
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
Note

For all the test cases, min(N,M)<=5, max(N,M)<=130.

Blue Mary's Note: The data has been enhanced on Feb.28, 2008 to avoid precalculated tables. Sorry to some users.
Added by:[Trichromatic] XilinX
Date:2007-12-01
Time limit:1.060s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel Pentium G860 3GHz)
Languages:All except: C99 strict ERL JS
Resource:IPSC 2007

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.