시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
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
13 121