题目描述

有一个无限大的网格图，在第$0$秒的时候，有$n$个格子会着火，每隔一秒，一个着火的格子会导致和它八连通的未着火的格子着火，没有着火的格子权值为 0，定义一个着火格子的权值为它最早着火的时间，求 $t$ 秒之后所有着火格子的权值和 $\text{mod 998244353}$ 。

输入格式

第一行输入一个正整数$T$，表示有$T$组数据 接下来对于每组数据输入两个正整数 $n,t$，接下来 $n$ 行，每行输入一个坐标 $(x,y)$，表示一开始 $(x,y)$ 会着火，题目保证每个点的坐标互不相同。

输出格式

输出 $T$ 行表示答案。

样例输入1

1
1 2
10 11

样例输出1

40

样例输入2

1
4 1
2 2
1 3
0 2
2 4

样例输出2

18

数据规模和约定

对于所有测试点均满足$T,\sum n≤2000,t≤10^8,-10^8≤x_{i},y_{i}≤10^8$