题目描述

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

$$\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} (i \mathrm{xor} j) $$

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

也就是说，k 个时间单位后，整个表格储存的总能量是

$$\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} \mathrm{max} ((i \mathrm{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

提示

测试点 1 ~ 2：$T = 5000$，$n \leq 100$，$m \leq 100$，$k \leq 100$，$p \leq 10 ^ 9$；

测试点 3：$T = 5000$，$n \leq 10 ^ {18}$，$m \leq 10 ^ {18}$，$k = 0$，$p \leq 10 ^ 9$；

测试点 4：$T = 5000$，$n \leq 10 ^ {18}$，$m \leq 10 ^ {18}$，$k = 1$，$p \leq 10 ^ 9$；

测试点 5：$T = 5000$，$n \leq 10$，$m \leq 10 ^ {18}$，$k \leq 10$，$p \leq 10 ^ 9$；

测试点 6：$T = 1$，$n \leq 10 ^ 5$，$m \leq 10 ^ {18}$，$k \leq 10 ^ 5$，$p \leq 10 ^ 9$；

测试点 7：$T = 1$，$n \leq 10 ^ {18}$，$m \leq 10 ^ {18}$，$k \leq 10 ^ {18}$，$p \leq 10 ^ 9$；

测试点 8：$T = 100$，$n \leq 10 ^ {18}$，$m \leq 10 ^ {18}$，$k \leq 10 ^ {18}$，$p \leq 10 ^ 9$；

测试点 9 ~ 10：$T = 5000$，$n \leq 10 ^ {18}$，$m \leq 10 ^ {18}$，$k \leq 10 ^ {18}$，$p \leq 10 ^ 9$ 。