Description

There is a table with $n$ rows and $m$ columns, with rows numbered from $0$ to $n-1$ and columns numbered from $0$ to $m-1$. Each cell stores energy. Initially, the cell in row $i$ and column $j$ stores $(i \oplus j)$ units of energy (where $\oplus$ denotes bitwise XOR). Therefore, the total energy stored in the whole table is

$$\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} i \oplus j.$$

As time passes, the energy in the cells gradually decreases. After each unit of time, the energy in every cell decreases by $1$. Obviously, once a cell’s energy decreases to $0$, it will not decrease any further.

That is, after $k$ units of time, the total energy stored in the whole table is

$$\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} \max((i \oplus j)-k,0).$$

Given the table, find the total energy it stores after $k$ units of time.

Since the total energy may be large, output it modulo $p$.

Input Format

The first line contains an integer $T$, the number of test cases. Then $T$ lines follow, each containing four integers $n, m, k, p$.

Output Format

Output $T$ lines, each containing one number: the result of the total energy modulo $p$.

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

2
12
6

Hint

For $100\%$ of the testdata, it is guaranteed that $1 \le T \le 5000$, $1 \le p \le 10^9$, $1 \le n,m \le 10^{18}$, $0 \le k \le 10^{18}$.

测试点编号	$T=$	$n\le$	$m\le$	$k\le$	$p\le$
$1,2$	$5000$	$100$			$10^9$
$3$		$10^{18}$	$10^{18}$	$0$
$4$				$1$
$5$		$10$		$10$
$6$	$1$	$10^5$		$10^5$
$7$		$10^{18}$		$10^{18}$
$8$	$100$
$9,10$	$5000$

$\texttt{Statement fixed by Starrykiller.}$

Translated by ChatGPT 5