题目描述

有一个 $n$ 行 $m$ 列的表格，行从 $0$ 到 $n−1$ 编号，列从 $0$ 到 $m−1$ 编号。每个格子都储存着能量。最初，第 $i$ 行第 $j$ 列的格子储存着 $i\ \text{xor}\ j$ 点能量。所以，整个表格储存的总能量是 $\sum_{i=0}^{n-1}\sum_{j=0}^{m-1}(i\ \text{xor}\ j)$。

随着时间的推移，格子中的能量会渐渐减少。一个时间单位，每个格子中的能量都会减少 $1$。显然，一个格子的能量减少到 $0$ 之后就不会再减少了。

也就是说，$k$ 个时间单位后，整个表格储存的总能量是 $\sum_{i = 0}^{n - 1} \sum_{j = 0}^{m - 1} \max ((i\ \text{xor}\ j) - k, 0)$。

给出一个表格，求 $k$ 个时间单位后它储存的总能量。由于总能量可能较大，输出时对 $p$ 取模。

输入格式

第一行一个整数 $T$，表示数据组数。接下来 $T$ 行，每行四个整数 $n,m,k,p$。

输出格式

共 $T$ 行，每行一个数，表示总能量对 $p$ 取模后的结果

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

2
12
6

提示

$T \le 5000, n, m, k \le 10^{18}, p \le 10^9$