There is a table with $n$ rows and $m$ columns, where rows are numbered from $0$ to $n-1$ and columns are numbered from $0$ to $m-1$. Each cell stores energy. Initially, the cell at row $i$ and column $j$ stores $(i \text{ xor } j)$ units of energy. Therefore, the total energy stored in the entire table is: $$\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} (i \text{ xor } j)$$

As time passes, the energy in the cells gradually decreases. In one time unit, the energy in each cell decreases by $1$. Obviously, once a cell's energy reaches $0$, it will not decrease further. That is to say, after $k$ time units, the total energy stored in the entire table is: $$\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} \max((i \text{ xor } j) - k, 0)$$

Given a table, find the total energy stored after $k$ time units. Since the total energy can be large, output the result modulo $p$.

Input

The first line contains an integer $T$, representing the number of test cases. The next $T$ lines each contain four integers $n, m, k, p$.

Output

There are $T$ lines in total, each containing one number representing the result of the total energy modulo $p$.

Examples

Input 1

3
2 2 0 100
3 3 0 100
3 3 1 100

Output 1

2
12
6