题目描述

俗话说，自古枪兵幸运 E。而身为幸运 E 的 L 叔最想要的，就是 C 妈的金羊毛了。然而这显然不是那么容易达成的。为了防止入侵者，C 妈花费了 $k$ 单位魔力，建造了包含了若干个消耗一单位魔力的小型防御设施和消耗两单位魔力的大型防御设施。

经过很长时间的调查，L 叔终于了解到了 C 妈可能采用的小型防御设施有 $n$ 种，大型防御设施有 $m$ 种。每一种都可以建造任意个数个。由于 L 叔拥有 Rune 文字的加持和 B 级别的对魔力，只要了解每一种防御设施的数量，就可以破解这样的防御。

然而，因为 L 叔的幸运是 E，所以他只有在尝试每一种方案之后才能找到破解的方法。他找到你，想让你判断一下他要尝试多少次才找到破解方法。由于凯尔特神话中对数字的迷信，你只要输出答案模 $p$ 的值就可以了。

输入格式

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

输出格式

$T$ 行每行一个整数，表示答案模 $p$ 的值。

样例输入

3
0 10 2 47
2 2 4 47
5 5 10 47

样例输出

10
14
6

提示

对于 $100\%$ 的数据，$1 \le T \le 20$，$1 \le n,m \le 10^5$，$1 \le k \le 10 ^ {12}$，$1 \le p \le 10 ^ 6$，$p$ 为质数。