题目描述

给你两种操作 $op$ 以及三个数 $abc$：

• $op=1$ 求 $a$ 到 $b$ 之间所有数的和除以 $c$ 的余数。
• $op=2$ 求 $a$ 到 $b$ 之间所有数的积除以 $c$ 的余数。

输入格式

第一行一个整数 $n$，代表测试数据的组数（不超过 $100$）。 接下来 $n$ 行，每行 $4$ 个正整数 $op,a,b,c$。

$1 \leq a \leq b \leq 10^6$

$1 \leq c \leq 10^9$

输出格式

对每组输入，输出其运算结果。

3
1 3562 102208 485597135
2 531591 586771 592771607
2 1 30 1000000007

360975245
0
109361473

样例解释

$3562+3563+\dots +102208=5220008095，5220008095\%485597135=360975245$

第三个式子连乘结果为$8841761993739701954543616000000$