Dana jest siatka o $n$ wierszach i $m$ kolumnach. Każda komórka siatki zawiera liczbę całkowitą, gdzie $a_{i,j}$ oznacza liczbę w komórce znajdującej się w $i$-tym wierszu i $j$-tej kolumnie.

Niech $(i, j)$ oznacza komórkę znajdującą się w $i$-tym wierszu i $j$-tej kolumnie. Startujesz z $(1, 1)$ i musisz dotrzeć do $(n, m)$. Będąc w komórce $(i, j)$, możesz przejść do komórki po prawej stronie $(i, j + 1)$, jeśli $j < m$, lub do komórki poniżej $(i + 1, j)$, jeśli $i < n$.

Niech $\mathbb{S}$ będzie zbiorem składającym się z liczb całkowitych znajdujących się w każdej komórce na Twojej ścieżce, wliczając $a_{1,1}$ oraz $a_{n,m}$. Wartość ścieżki definiuje się jako liczbę elementów w $\mathbb{S}$ (przypomnijmy, że zbiory nie zawierają powtarzających się elementów). Oblicz sumę wartości wszystkich możliwych ścieżek.

Wejście

Dostępnych jest wiele zestawów danych testowych. Pierwsza linia wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 10^3$) określającą liczbę zestawów danych. Dla każdego zestawu danych:

Pierwsza linia zawiera dwie liczby całkowite $n$ oraz $m$ ($1 \le n, m \le 10^5$, $1 \le n \times m \le 10^5$) określające liczbę wierszy i kolumn siatki.

W kolejnych $n$ liniach, $i$-ta linia zawiera $m$ liczb całkowitych $a_{i,1}, a_{i,2}, \dots, a_{i,m}$ ($1 \le a_{i,j} \le n \times m$), gdzie $a_{i,j}$ oznacza liczbę w komórce $(i, j)$.

Gwarantuje się, że suma $n \times m$ dla wszystkich zestawów danych nie przekroczy $10^5$.

Wyjście

Dla każdego zestawu danych wypisz w jednej linii liczbę całkowitą oznaczającą sumę wartości wszystkich możliwych ścieżek. Ponieważ wynik może być duży, wypisz go modulo $998\,244\,353$.

Przykład

Wejście 1

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

Wyjście 1

7
1
3

Uwagi

Dla pierwszego przykładowego zestawu danych istnieją 3 możliwe ścieżki:

• Pierwsza ścieżka to $(1, 1) \to (1, 2) \to (1, 3) \to (2, 3)$. $\mathbb{S} = \{1, 2, 5\}$.
• Druga ścieżka to $(1, 1) \to (1, 2) \to (2, 2) \to (2, 3)$. $\mathbb{S} = \{2, 5\}$.
• Trzecia ścieżka to $(1, 1) \to (2, 1) \to (2, 2) \to (2, 3)$. $\mathbb{S} = \{1, 5\}$.

Zatem wynik to $3 + 2 + 2 = 7$.