eolymp
bolt
Try our new interface for solving problems
Problems

A Piece of Paper

A Piece of Paper

Time limit 1 second
Memory limit 64 MiB

In the ancient Persian, Parviz, the king of the kingdom, had prepared an annual Nowrooz ceremony in his palace and invited all of the rulers of his kingdom. Ruler of Jey had brought Parviz, a small valuable cotton-surfaced rectangular-shaped paper with the words of Parviz’s Unspeakable Immortality (UI) on it. Parviz ordered a slave to put it in the jewelry box but the slave (that didn’t know value of UI paper) first folded the paper. Parviz saw it and angrily picked up a bow and shooted an arrow aimed at the poor slave but the arrow passed through the folded paper and made a hole on it. Your job is to find out the number of holes when the paper is unfolded.

Input data

The first line of input contains an integer, the number of test cases. Each test case begins with a line containing five integers: R and T, the right and top coordinates of original paper, HX and HY, the coordinates of the hole in final folded paper (0 <= R, T, HX, HY <= 10000) and F (0 <= F <= 8), the number of folds, respectively. The left-bottom coordinate of paper is (0,0). Next F lines describe the folds that have been performed on the original paper sequentially and one by one. Each of these lines contains a character C and an integer I (0 <= I <= 10000); if the folding is performed vertically, C would be the "X" character and the right portion of the paper folds over left portion (by the line x = I) and if it’s performed horizontally, C would be the "Y" character and the top portion of the paper folds over bottom portion (by the line y = I). Note that a hole on the border of the paper is treated inside of that paper.

Output data

There should be one line for each test case in output. Each line should contain a single integer which should be the number of holes on the original paper when it’s unfolded.

Examples

Input example #3
2
1000 1000 20 20 2
X 20
Y 20
1000 1000 15 10 2
X 20
Y 20
Output example #3
1
4