Description

小象喜欢为箱子涂色。小象现在有c 种颜色，编号为$[0, c − 1]$。 还有$n$个箱子，编号为$[1, n]$，最开始每个箱子的颜色为$1$。 小象涂色时喜欢遵循灵感：它将箱子按编号排成一排，每次涂色时，它随机选择$[L,R]$ 这个区间里的一些箱子（不选看做选$0$ 个），为之涂上随机一种颜色。 若一个颜色为$a$ 的箱子被涂上$b$ 色，那么这个箱子的颜色会变成$(a×b) mod c$。请问在$k$ 次涂色后，所有箱子颜色的编号和期望为多少？

Format

Input

第一行为$T$，表示有$T$组测试数据。 对于每组数据，第一行为三个整数$n,c,k$。 接下来$k$行，每行两个整数$L_i,R_i$，表示第$i$个操作的$L$和$R$。

Output

对于每组测试数据，输出所有箱子颜色编号和的期望值，结果保留$9$位小数.

Samples

3
3 2 2
2 2
1 3
1 3 1
1 1
5 2 2
3 4
2 4

2.062500000
1.000000000
3.875000000

Limitation

对于所有测试点：

40%的数据$1 \le T \le 5,1 \le n, k \le 15,2 \le c \le 20$

100%的数据满足$1 \le T \le 10,1 \le n, k \le 50,2 \le c \le 100,1 \le L_i \le R_i \le n$