|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||128 MB||0||0||0||0.000%|
The great Dutch painter Piet Mondriaan (1872–1944) is considered one of the first modern painters. A major part of his compositions is divided in a couple of rectangular regions. Some of them are filled with a color, while the remaining ones are left white.
Mondriaan’s colorings usually obeyed the following rules:
Once a painting is divided in regions, there are still a lot of different ways to fill these with colors. Mondriaan is wondering how many different ways there are for a given division. For the paintings we consider, this number will not exceed 106.
Two regions that only touch at a corner point are not considered adjacent.
The first line of the input file contains a single number: the number of test cases to follow. Each test case has the following format:
For every test case in the input file, the output should contain a single number, on a single line: the number of ways the painting can be colored.
2 2 100 110 70 105 100 105 12345 110 4 0 0 1 1 0 1 1 2 1 0 2 1 1 1 2 2