Một robot lau dọn được đặt trên sàn của một căn phòng hình chữ nhật, xung quanh được bao bởi các bức tường. Sàn gồm ~n~ hàng và ~m~ cột. Các hàng của sàn được đánh số từ ~1~ đến ~n~ theo thứ tự từ trên xuống dưới, và các cột của sàn được đánh số từ ~1~ đến ~m~ theo thứ tự từ trái sang phải. Ô tại giao điểm của hàng thứ ~r~ và cột thứ ~c~ được ký hiệu là ~(r,c)~. Vị trí ban đầu của robot là ~(r_b, c_b)~.

Trong một giây, robot di chuyển ~dr~ hàng và ~dc~ cột; tức là sau một giây, robot đi từ ô ~(r, c)~ đến ô ~(r + dr, c + dc)~. Ban đầu, ~dr = 1~, ~dc = 1~. Nếu có một bức tường dọc (tường bên trái hoặc bên phải) theo hướng di chuyển, thì ~dc~ sẽ bị phản xạ trước khi di chuyển, nên giá trị mới của ~dc~ là ~-dc~. Tương tự, nếu có một bức tường ngang (tường phía trên hoặc phía dưới) theo hướng di chuyển, thì ~dr~ sẽ bị phản xạ trước khi di chuyển, nên giá trị mới của ~dr~ là ~-dr~.

Mỗi giây (bao gồm cả thời điểm trước khi robot bắt đầu di chuyển), robot sẽ lau sạch mọi ô nằm trên cùng hàng hoặc cùng cột với vị trí hiện tại của nó. Nhiệm vụ của robot là lau sạch toàn bộ sàn; tức là mỗi ô trên sàn cần được lau ít nhất một lần.

Cho kích thước sàn ~n~ và ~m~, cùng vị trí ban đầu của robot ~(r_b, c_b)~, hãy tìm thời gian để robot hoàn thành nhiệm vụ.

Input

Mỗi bộ dữ liệu gồm nhiều test case. Dòng đầu tiên chứa số lượng test case ~t~ (~1 \le t \le 10^4~). Phần mô tả các test case như sau.

Mỗi test case chỉ gồm một dòng, chứa bốn số nguyên ~n~, ~m~, ~r_b~, ~c_b~ (~2 \le n, m \le 100~, ~1 \le r_b \le n~, ~1 \le c_b \le m~) — kích thước của căn phòng và vị trí ban đầu của robot.

Output

Với mỗi test case, in ra một số nguyên — thời gian để robot lau sạch toàn bộ sàn. Có thể chứng minh rằng cuối cùng mọi ô trên sàn đều sẽ được lau ít nhất một lần.

Scoring

Tổng điểm cho bài này là ~500~.

Sample Input 1

5
10 10 6 1
10 10 9 9
9 8 5 6
6 9 2 2
2 2 1 1

Sample Output 1

9
10
9
9
1

Notes

Trong ví dụ đầu tiên, sàn có kích thước ~10\times 10~. Vị trí ban đầu của robot là ~(6, 1)~. Hãy xem hình minh họa của ví dụ này trong đề bài.

Trong ví dụ thứ hai, sàn vẫn như cũ, nhưng vị trí ban đầu của robot bây giờ là ~(9, 9)~.

Trong ví dụ thứ ba, sàn có kích thước ~9 \times 8~. Vị trí ban đầu của robot là ~(5, 6)~.

Trong ví dụ thứ tư, sàn có kích thước ~6 \times 9~. Vị trí ban đầu của robot là ~(2, 2)~.

Trong ví dụ cuối cùng, sàn có kích thước ~2 \times 2~. Vị trí ban đầu của robot là ~(1, 1)~.

Cho hai dãy số nguyên ~a~ và ~b~, mỗi dãy gồm ~n~ phần tử, và một số nguyên ~k~.

Bạn được phép biến đổi dãy ~a~ bằng thao tác sau với số lần không giới hạn:

• Chọn một chỉ số ~i~ (~1 \le i < n~) sao cho ~a_i + a_{i + 1} = k~, và đổi chỗ hai phần tử ~a_i~ và ~a_{i+1}~.

Với hai dãy số ~a~ và ~b~ cho trước, hỏi có thể biến đổi dãy ~a~ thành dãy ~b~ hay không?

Input

Dòng đầu tiên chứa số nguyên ~t~ (~1 \le t \le 10^4~)  — số lượng test case. Mô tả mỗi test case như sau:

• Dòng đầu tiên chứa hai số nguyên ~n~, ~k~ (~1 \le n \le 2 \cdot 10^5~; ~|k| \le 10^9~).

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~|a_i| \le 10^9~).

• Dòng thứ ba chứa ~n~ số nguyên ~b_1, b_2, \ldots, b_n~ (~|b_i| \le 10^9~).

Đảm bảo rằng tổng ~n~ qua tất cả các test không vượt quá ~2 \cdot 10^5~.

Output

Với mỗi test, in ra YES nếu có thể biến đổi dãy ~A~ thành dãy ~B~, hoặc NO nếu không.

Scoring

Tổng điểm cho bài này là ~1000~.

Sample Input 1

5
5 5
1 4 1 2 3
4 1 1 3 2
3 -5
-1 -2 -4
-4 -2 -1
1 1000000000
-1000000000
1000000000
4 0
-1 1 -1 1
1 -1 1 -1
6 7
1 6 6 1 2 5
6 1 1 6 5 2

Sample Output 1

YES
NO
NO
YES
YES

Notes

Ở test case thứ nhất, ta có ~k = 5~ và ~a = [1, 4, 1, 2, 3]~. Ta có thể thực hiện thao tác sau để biến đổi dãy ~a~ thành ~b = [4, 1, 1, 3, 2]~:

• Đổi chỗ cặp phần tử đầu tiên: ~[\underline{1}, \underline{4}, 1, 2, 3] \Longrightarrow [4, 1, 1, 2, 3]~;

• Đổi chỗ cặp phần tử cuối cùng: ~[4, 1, 1, \underline{2}, \underline{3}] \Longrightarrow [4, 1, 1, 3, 2]~.

Ở test case thứ hai, ta có ~k = 5~, ~a = [-1, -2, -4]~ và ~b = [-4, -2, -1]~. Do không tồn tại cặp phần tử kề nhau có tổng là ~5~, ta không thể thực hiện phép biến đổi nào cả. Như vậy, đáp án là NO.

Đại tướng Thiên Quang chuẩn bị đối đầu với một cuộc tập kích quy mô lớn từ quân địch. Để thiết lập tuyến phòng thủ, Thiên Quang duyệt một đạo quân gồm ~n~ đơn vị đang xếp thành một hàng dọc, với chỉ số sức mạnh lần lượt là ~a_1, a_2, \ldots, a_n~.

Thiên Quang vô cùng tin tưởng và giao cho phó tướng Bá Lộc nhiệm vụ điều phối đạo quân này vào đúng ~k~ cứ điểm phòng ngự chiến lược. Do yêu cầu khắt khe về đội hình hành quân, Bá Lộc cần phải chia các đơn vị vào ~k~ cứ điểm thỏa mãn các điều kiện sau:

• mỗi cứ điểm phải có ít nhất một đơn vị;

• mỗi đơn vị phải thuộc về một cứ điểm;

• nếu đơn vị thứ ~i~ và đơn vị thứ ~j~ (~i < j~) thuộc cùng một cứ điểm, tất cả các đơn vị ~i, i + 1, i + 2, \ldots, j~ phải thuộc cùng một cứ điểm.

Sức mạnh phòng thủ của một cứ điểm là tổng chỉ số sức mạnh của các đơn vị thuộc cứ điểm đó.

Tin tình báo cho biết rằng mỗi đạo quân địch có sức mạnh là ~s~. Một cứ điểm được coi là mong manh nếu sức mạnh phòng thủ của cứ điểm này nhỏ hơn hoặc bằng ~s~.

Là một phó tướng tài, Bá Lộc muốn xem xét hết mọi trường hợp có thể xảy ra, kể cả trường hợp tệ nhất. Trong tất cả các cách điều phối đạo quân hợp lệ, hãy giúp Bá Lộc tìm xem số lượng cứ điểm mong manh nhiều nhất có thể điều phối được.

Input

Mỗi test gồm nhiều test case. Dòng đầu tiên của bộ dữ liệu chứa số nguyên dương ~t~ (~1 \le t \le 10^4~) — số lượng test case. Mô tả của mỗi test case như sau:

• Dòng đầu tiên chứa ba số nguyên ~n~, ~k~ và ~s~ (~1 \le k \le n~, ~1 \le s \le 10^9~) — số lượng đơn vị quân, số lượng cứ điểm cần phân bổ và sức mạnh tấn công của quân địch vào mỗi cứ điểm.

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^9~) — chỉ số sức mạnh của các đơn vị quân, theo thứ tự xếp hàng.

Output

Với mỗi test case, in ra một số nguyên — số lượng cứ điểm mong manh nhiều nhất có thể điều phối.

Scoring

Sample Input 1

3
5 3 10
1 2 3 4 5
7 3 10
3 12 5 7 15 2 8
4 2 5
1 2 3 4

Sample Output 1

3
2
1

Notes

Ở test case đầu tiên, Bá Lộc có thể điều phối đội hình thành ~k = 3~ cứ điểm ~[1, 2, 3], [4], [5]~. Sức mạnh phòng thủ các cứ điểm lần lượt là ~6~, ~4~ và ~5~, đều không quá ~s = 10~, nên có ~3~ cứ điểm mong manh.

Ở test case thứ hai, Bá Lộc có thể điều phối thành ~k = 3~ cứ điểm như sau: ~[3], [12, 5, 7, 15], [2, 8]~. Sức mạnh phòng thủ của các cứ điểm lần lượt là ~3~, ~39~ và ~10~. Đáp án là ~2~ do cứ điểm đầu tiên và cuối cùng có sức mạnh phòng thủ không quá ~s = 10~. Có thể chỉ ra rằng không có cách chia nào để cả ~3~ cứ điểm đều mong manh.

Ở test case thứ ba, một cách điều phối để có ~1~ cứ điểm mong manh là ~[1, 2], [3, 4]~. Không có cách điều phối nào để cả hai cứ điểm đều mong manh.

Đây là một bài toán tương tác (interactive)

Cho một cây nhị phân gồm ~2\cdot n - 1~ đỉnh được đánh số từ ~1~ đến ~2\cdot n - 1~. Gốc cây là đỉnh ~2\cdot n - 1~. Trên cây, các đỉnh ~1, 2, \ldots, n~ là các đỉnh lá. Các đỉnh ~p~ (~n < p < 2\cdot n~) còn lại đều thoả mãn tính chất sau:

• đỉnh ~p~ có chính xác hai đỉnh con, một đỉnh con bên trái ~a_p~ và một đỉnh con bên phải ~b_p~;

• với cặp đỉnh lá ~u~, ~v~ (~1 \le u, v \le n~) bất kì mà ~a_p~ là tổ tiên^∗ của ~u~ và ~b_p~ là tổ tiên của ~v~, thì ~u < v~.

Với ~1 \le l \le r \le n~, định nghĩa ~f(l, r)~ là số lượng phần tử của tập hợp các đỉnh ~S~ thoả mãn các điều kiện sau:

• với ~l \le u \le r~, tồn tại một tổ tiên của ~u~ trong ~S~;

• với ~1 \le u < l~ hoặc ~r < u \le n~, không tồn tại tổ tiên nào của ~u~ trong ~S~;

• trong tất cả các tập hợp đỉnh thoả mãn hai điều kiện trên, tập ~S~ là tập có ít phần tử nhất.

Bạn được biết số nguyên ~n~, nhưng không biết trước cấu trúc của cây. Bạn cần tương tác với chương trình của ban tổ chức (BTC) để xác định cấu trúc của cây nhị phân. Bạn được phép đưa ra các truy vấn có dạng ~l, r~ (~1 \le l \le r \le n~), và phản hồi bạn nhận được là ~f(l, r)~.

Khi đã xác định được cấu trúc cây, bạn cần đưa ra danh sách các đỉnh con ~a_p~ và ~b_p~ cho các đỉnh ~n < p < 2 \cdot n~. Đáp án của bạn được coi là đúng khi các điều kiện sau thoả mãn:

• bạn đưa ra không quá ~n^2~ truy vấn;

• cấu trúc cây thoả mãn các tính chất đã nêu trên;

• với mọi cặp số ~l, r~ (~1 \le l \le r \le n~), ~f(l, r)~ tính từ cây của bạn phải bằng với ~f(l, r)~ tính từ cây của BTC.

Nếu có nhiều đáp án thoả mãn các điều kiện trên, hãy đưa ra đáp án thoả mãn bất kì.

Trong bài toán này, điểm số bạn nhận được phụ thuộc vào số lượng truy vấn bạn đưa ra. Chi tiết xem thêm phần scoring.

∗ Đỉnh ~p~ được gọi là tổ tiên của ~u~ nếu ~p = u~, hoặc ~p~ không phải là lá và một đỉnh con của ~p~ là tổ tiên của ~u~.

Interaction

Đầu tiên, bạn cần đọc số nguyên ~t~ (~1 \le t \le 150~)  – số test case. Với mỗi test case, quá trình tương tác diễn ra như sau:

• Đầu tiên, hãy đọc vào một số nguyên ~n~ (~2 \le n \le 150~) – số lượng đỉnh lá của cây.

• Để đưa ra truy vấn, hãy in ra ? ~l \ r~ (~1 \le l \le r \le n~), sau đó đọc vào một số nguyên ~f(l, r)~.

• Khi đã xác định được cấu trúc của cây, hãy in ra trên một dòng kí tự !, tiếp đó in ra ~2n - 2~ số nguyên ~a_{n+1}, b_{n+1}, a_{n+2}, b_{n+2}, \ldots, a_{2n-1}, b_{2n-1}~ – danh sách các đỉnh con của các đỉnh ~n + 1, n + 2, \ldots 2 \cdot n - 1~.

  Nếu có nhiều đáp án đúng, hãy in ra đáp án bất kì.

Cây đã được cố định trước quá trình tương tác, và sẽ không thay đổi trong quá trình tương tác.

Dữ liệu vào đảm bảo tổng giá trị ~n~ của các testcase không vượt quá ~150~.

Sau khi in ra một câu lệnh, đừng quên xuống dòng và flush đầu ra chuẩn. Để làm điều này, bạn có thể sử dụng:

• fflush(stdout) hoặc cout.flush() trong C++;

• System.out.flush() trong Java;

• flush(output) trong Pascal;

• stdout.flush() trong Python;

• xem tài liệu chuẩn đối với các ngôn ngữ khác.

Scoring

Gọi ~q~ là số câu hỏi bạn đưa ra. Điểm số của bạn cho test case như sau:

Điểm số của bộ dữ liệu vào bằng điểm số thấp nhất của các test case. Điểm số của bạn cho bài này bằng điểm số thấp nhất của các bộ dữ liệu vào.

Sample Input 1

2
3

2

1

4

2

2

1

Sample Output 1

? 1 2

? 2 3

! 2 3 1 4

? 1 3

? 2 4

? 1 4

! 1 2 3 4 5 6

Notes

Trong ví dụ đầu tiên, các truy vấn được đưa ra như sau:

• ~f(1, 2) = 2~. Ở đây ~S = \{ 1, 2 \}~

• ~f(2, 3) = 1~. Ở đây ~S = \{ 4 \}~

Trong ví dụ thứ hai, các truy vấn được đưa ra như sau:

• ~f(1, 3) = 2~. Ở đây ~S = \{ 3, 6 \}~

• ~f(2, 4) = 2~. Ở đây ~S = \{ 2, 5 \}~

• ~f(1, 4) = 1~. Ở đây ~S = \{ 7 \}~

Tahp đang nghiên cứu một cách biểu diễn hoán vị^∗ bằng một dãy số nguyên. Cụ thể, xét một hoán vị ~p_1, p_2, \ldots, p_n~ của các số nguyên từ ~1~ đến ~n~. Với mỗi vị trí ~i~, Tahp định nghĩa một giá trị ~f_i~ như sau:

$$f_i = |\{j \mid 1 \le j < i,\ p_j < p_i\}|$$

Nói cách khác, ~f_i~ là số lượng phần tử đứng trước vị trí ~i~ trong hoán vị ~p~ nhưng có giá trị nhỏ hơn ~p_i~.

Ví dụ, nếu ~p = [2, 6, 4, 1, 5, 3]~, thì:

• ~f_1 = 0~, vì trước vị trí ~1~ không có phần tử nào.

• ~f_2 = 1~, vì trước ~p_2 = 6~ có một phần tử nhỏ hơn nó, đó là ~2~.

• ~f_3 = 1~, vì trước ~p_3 = 4~ có một phần tử nhỏ hơn nó, đó là ~2~.

• ~f_4 = 0~, vì trước ~p_4 = 1~ không có phần tử nào nhỏ hơn nó.

• ~f_5 = 3~, vì trước ~p_5 = 5~ có ba phần tử nhỏ hơn nó, đó là ~2, 4, 1~.

• ~f_6 = 2~, vì trước ~p_6 = 3~ có hai phần tử nhỏ hơn nó, đó là ~2, 1~.

Do đó, dãy ~f~ tương ứng với hoán vị trên là ~[0, 1, 1, 0, 3, 2]~.

Rõ ràng, với mọi hoán vị ~p~, dãy ~f~ thu được luôn thỏa mãn: ~0 \le f_i < i~. Điều thú vị là chiều ngược lại cũng đúng. Với mọi dãy số nguyên ~f_1, f_2, \ldots, f_n~ thỏa mãn ~0 \le f_i < i~, có thể chứng minh rằng tồn tại duy nhất một hoán vị ~p_1, p_2, \ldots, p_n~ sao cho dãy ~f~ được định nghĩa từ ~p~ theo công thức trên.

Trong bài toán này, bạn được cho dãy ~f~ ban đầu. Sau đó, dãy ~f~ sẽ thay đổi qua các thao tác cập nhật. Sau mỗi lần cập nhật, dữ liệu luôn đảm bảo rằng dãy ~f~ vẫn thỏa mãn ~0 \le f_i < i~, vì vậy hoán vị tương ứng với dãy ~f~ hiện tại luôn tồn tại và là duy nhất.

Bạn cần xử lý ~q~ thao tác. Mỗi thao tác thuộc một trong ba dạng sau:

• + i: tăng ~f_i~ lên ~1~.

• - i: giảm ~f_i~ đi ~1~.

• ? l r: xét hoán vị ~p~ duy nhất tương ứng với dãy ~f~ hiện tại, hãy in ra giá trị ~p_l + p_{l+1} + \cdots + p_r~.

∗ Một hoán vị độ dài ~n~ là một dãy gồm ~n~ số nguyên, trong đó mỗi số nguyên từ ~1~ đến ~n~ xuất hiện đúng một lần.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ ~(2 \le n \le 5 \cdot 10^5;\ 1 \le q \le 5 \cdot 10^5)~  — độ dài dãy ~f~ và số lượng thao tác.

Dòng thứ hai chứa ~n~ số nguyên ~f_1, f_2, \ldots, f_n~ ~(0 \le f_i < i~ với mọi ~1 \le i \le n)~.

Mỗi dòng trong ~q~ dòng tiếp theo mô tả một thao tác thuộc một trong ba dạng sau:

• + i ~(1 \le i \le n)~: tăng ~f_i~ lên ~1~.

• - i ~(1 \le i \le n)~: giảm ~f_i~ đi ~1~.

• ? l r ~(1 \le l \le r \le n)~: yêu cầu tính tổng ~p_l + p_{l+1} + \cdots + p_r~, trong đó ~p~ là hoán vị duy nhất tương ứng với dãy ~f~ hiện tại.

Đảm bảo tại mọi thời điểm, dãy ~f~ vẫn thỏa mãn ~0 \le f_j < j~ với mọi ~1 \le j \le n~, và có ít nhất một thao tác truy vấn ?.

Output

Với mỗi thao tác dạng ? l r, in ra trên một dòng một số nguyên là giá trị ~p_l + p_{l+1} + \cdots + p_r~, trong đó ~p~ là hoán vị duy nhất tương ứng với dãy ~f~ hiện tại.

Scoring

Sample Input 1

6 10
0 1 1 0 3 2
? 2 5
+ 4
- 5
+ 3
- 2
? 1 4
+ 6
- 4
+ 5
? 2 5

Sample Output 1

16
14
14

Notes

Ban đầu, dãy ~f~ là ~[0, 1, 1, 0, 3, 2]~. Hoán vị tương ứng là ~p = [2, 6, 4, 1, 5, 3]~. Do đó, truy vấn ? 2 5 có đáp án ~p_2 + p_3 + p_4 + p_5 = 6 + 4 + 1 + 5 = 16~.

Sau các thao tác + 4, - 5, + 3, - 2, dãy ~f~ trở thành ~[0, 0, 2, 1, 2, 2]~. Hoán vị tương ứng lúc này là ~p = [5, 1, 6, 2, 4, 3]~. Vì vậy, truy vấn ? 1 4 có đáp án ~p_1 + p_2 + p_3 + p_4 = 5 + 1 + 6 + 2 = 14~.

Sau các thao tác + 6, - 4, + 5, dãy ~f~ trở thành ~[0, 0, 2, 0, 3, 3]~. Hoán vị tương ứng lúc này là ~p = [3, 2, 6, 1, 5, 4]~. Vì vậy, truy vấn cuối cùng ? 2 5 có đáp án ~p_2 + p_3 + p_4 + p_5 = 2 + 6 + 1 + 5 = 14~.

Với một hoán vị ~a~ ^∗ độ dài ~n~, định nghĩa ma trận MEX của dãy ~a~ là ma trận ~M~ có kích thước ~n \times n~, trong đó giá trị của phần tử ~M_{i, j}~ được xác định như sau:

• ~M_{i, j} = mex\left(a_i, a_{i + 1}, \dots, a_j\right)~ ^† với ~i \le j~;

• ~M_{i, j} = -1~ với ~i > j~.

Một hoán vị ~a~ độ dài ~n~ được gọi là ~k~-good (~0 \le k < n~) nếu không tồn tại hoán vị ~b~ độ dài ~n~ sao cho:

• Vị trí của phần tử có giá trị ~k~ trong hoán vị ~a~ khác với vị trí của phần tử có giá trị ~k~ trong hoán vị ~b~.

• Ma trận MEX của hai hoán vị ~a~ và ~b~ giống nhau.

Cho dãy số nguyên ~a'_1, a'_2, \ldots, a'_n~ (~-1 \le a'_i < n~). Với mọi ~k~ từ ~0~ đến ~n - 1~, hãy đếm số lượng hoán vị ~a~ độ dài ~n~ thỏa mãn:

• Với mọi ~i~ từ ~1~ đến ~n~, nếu ~a'_i \ne -1~ thì ~a_i = a'_i~;

• ~a~ là hoán vị ~k~-good.

Vì kết quả có thể rất lớn, hãy in ra các đáp án sau khi chia lấy dư cho ~998\ 244\ 353~.

∗ Một hoán vị độ dài ~n~ là dãy số bao gồm ~n~ số nguyên không âm phân biệt có giá trị từ ~0~ đến ~n-1~ được sắp xếp theo thứ tự bất kỳ. Ví dụ, ~[1, 2, 0, 4, 3]~ là một hoán vị có độ dài ~n=5~, tuy nhiên ~[0, 1, 1]~ không phải là hoán vị (~1~ xuất hiện hai lần trong dãy), và ~[2, 1, 3]~ cũng không phải là hoán vị (~n=3~ nhưng lại xuất hiện số ~3~ trong dãy).

† Giá trị ~mex~ của một dãy số nguyên là số nguyên không âm nhỏ nhất không xuất hiện trong dãy. Ví dụ:

• Giá trị ~mex~ của dãy ~[2, 2, 1]~ bằng ~0~, vì ~0~ không xuất hiện trong dãy.

• Giá trị ~mex~ của dãy ~[3, 1, 0, 1]~ bằng ~2~, vì ~0~ và ~1~ xuất hiện trong dãy, nhưng ~2~ thì không.

• Giá trị ~mex~ của dãy ~[0, 3, 1, 2]~ bằng ~4~, vì ~0,1,2,3~ xuất hiện trong dãy, nhưng ~4~ thì không.

Input

Dòng đầu tiên chứa số nguyên ~t~ (~1 \le t \le 5000~) — số lượng test case. Mô tả của mỗi test case như sau:

• Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 5000~) — kích thước của dãy ~a'~.

• Dòng thứ hai chứa ~n~ số nguyên ~a'_1, a'_2, \dots, a'_n~ (~-1 \le a'_i < n~). Đảm bảo các phần tử có giá trị không âm chỉ xuất hiện một lần trong dãy ~a'~.

Đảm bảo rằng tổng ~n~ qua tất cả các test case không vượt quá ~5000~.

Output

Với mỗi test case, hãy in ra ~n~ số nguyên, trong đó số thứ ~i~ là số lượng dãy ~a~ thỏa mãn điều kiện đề bài tương ứng với ~k = i - 1~. Vì kết quả có thể rất lớn, hãy in ra các đáp án sau khi chia lấy dư cho ~998\ 244\ 353~.

Scoring

Sample Input 1

6
1
-1
2
-1 0
3
-1 -1 -1
4
2 3 -1 -1
5
-1 1 -1 4 -1
6
3 -1 5 4 -1 -1

Sample Output 1

1 
1 1 
6 6 6 
2 2 2 2 
6 6 5 4 3 
6 6 4 6 0 0

Notes

Trong ba test case đầu tiên, có thể chỉ ra rằng tất cả hoán vị độ dài ~n \le 3~ đều là hoán vị ~k~-good với mọi ~k~ từ ~0~ đến ~n - 1~. Vì thế:

• Trong test case thứ nhất, chỉ có ~1~ hoán vị ~a~ có thể tạo ra từ dãy ~a'~ là ~[0]~ nên đáp án cho test case này với ~k = 0~ là ~1~.

• Trong test case thứ hai, chỉ có ~1~ hoán vị ~a~ có thể tạo ra từ dãy ~a'~ là ~[1, 0]~ nên đáp án cho test case này với ~k = 0, 1~ là ~1~.

• Trong test case thứ ba, có ~6~ hoán vị ~a~ có thể tạo ra từ dãy ~a'~ là ~[0, 1, 2]~; ~[0, 2, 1]~; ~[1, 0, 2]~; ~[1, 2, 0]~; ~[2, 0, 1]~ và ~[2, 1, 0]~ nên đáp án cho test case này với ~k = 0, 1, 2~ là ~6~.

Trong test case thứ tư, từ dãy ~a'~ có thể tạo ra hai hoán vị ~a~ khác nhau là: ~[2,3,0,1]~; ~[2,3,1,0]~, với ma trận MEX lần lượt như sau: $$\begin{array}{cc} \begin{array}{|r|r|r|r|} \hline 0 & 0 & 1 & 4 \\ \hline \color{grey}{-1} & 0 & 1 & 2 \\ \hline \color{grey}{-1} & \color{grey}{-1} & 1 & 2 \\ \hline \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & 0 \\ \hline \end{array} & \begin{array}{|r|r|r|r|} \hline 0 & 0 & 0 & 4 \\ \hline \color{grey}{-1} & 0 & 0 & 2 \\ \hline \color{grey}{-1} & \color{grey}{-1} & 0 & 2 \\ \hline \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & 1 \\ \hline \end{array} \\ \end{array}$$

Có thể chỉ ra rằng không có hoán vị ~b \ne a~ nào cho ra hai ma trận MEX trên, nên mọi hoán vị ~a~ tạo được đều là hoán vị ~k~-good với mọi ~k~ từ ~0~ đến ~n - 1~. Đáp án cho test case này với ~k = 0, 1, 2, 3~ đều là ~2~.

Trong test case thứ năm, có thể tạo ra sáu hoán vị ~a~ khác nhau là: ~[0, 1, 2, 4, 3]~; ~[0, 1, 3, 4, 2]~; ~[2, 1, 0, 4, 3]~; ~[2, 1, 3, 4, 0]~; ~[3, 1, 0, 4, 2]~ và ~[3, 1, 2, 4, 0]~, với ma trận MEX lần lượt như sau:

$$\begin{array}{ccccc} \begin{array}{|r|r|r|r|r|} \hline 1 & 2 & 3 & 3 & 5 \\ \hline \color{grey}{-1} & 0 & 0 & 0 & 0 \\ \hline \color{grey}{-1} & \color{grey}{-1} & 0 & 0 & 0 \\ \hline \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & 0 & 0 \\ \hline \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & 0 \\ \hline \end{array} & \begin{array}{|r|r|r|r|r|} \hline 1 & 2 & 2 & 2 & 5 \\ \hline \color{grey}{-1} & 0 & 0 & 0 & 0 \\ \hline \color{grey}{-1} & \color{grey}{-1} & 0 & 0 & 0 \\ \hline \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & 0 & 0 \\ \hline \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & 0 \\ \hline \end{array} & \begin{array}{|r|r|r|r|r|} \hline 0 & 0 & 3 & 3 & 5 \\ \hline \color{grey}{-1} & 0 & 2 & 2 & 2 \\ \hline \color{grey}{-1} & \color{grey}{-1} & 1 & 1 & 1 \\ \hline \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & 0 & 0 \\ \hline \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & 0 \\ \hline \end{array} & \end{array}$$

$$\begin{array}{ccccc} \begin{array}{|r|r|r|r|r|} \hline 0 & 0 & 0 & 0 & 5 \\ \hline \color{grey}{-1} & 0 & 0 & 0 & 2 \\ \hline \color{grey}{-1} & \color{grey}{-1} & 0 & 0 & 1 \\ \hline \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & 0 & 1 \\ \hline \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & 1 \\ \hline \end{array} & \begin{array}{|r|r|r|r|r|} \hline 0 & 0 & 2 & 2 & 5 \\ \hline \color{grey}{-1} & 0 & 2 & 2 & 3 \\ \hline \color{grey}{-1} & \color{grey}{-1} & 1 & 1 & 1 \\ \hline \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & 0 & 0 \\ \hline \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & 0 \\ \hline \end{array} & \begin{array}{|r|r|r|r|r|} \hline 0 & 0 & 0 & 0 & 5 \\ \hline \color{grey}{-1} & 0 & 0 & 0 & 3 \\ \hline \color{grey}{-1} & \color{grey}{-1} & 0 & 0 & 1 \\ \hline \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & 0 & 1 \\ \hline \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & 1 \\ \hline \end{array} & \end{array}$$

• Với ~k = 0~ và ~k = 1~, mọi hoán vị ~a~ tạo được đều là hoán vị ~0~-good và ~1~-good nên đáp án là ~6~.

• Với ~k = 2~, đáp án là ~5~ do có hoán vị ~a~ sau không thỏa mãn:

  • Hoán vị ~a = [3, 1, {\color{red}{2}}, 4, 0]~ và ~b = [3, 1, 4, {\color{red}{2}}, 0]~ đều cho ra cùng ma trận MEX, nhưng ~a_2 = b_3 = 2~ ở vị trí khác nhau;

  Các hoán vị ~a~ còn lại đều là hoán vị ~2~-good.

• Với ~k = 3~, đáp án là ~4~. Dưới đây là các cặp dãy ~a~ và ~b~ cho ra cùng ma trận MEX nhưng vị trí của giá trị ~3~ khác nhau:

  • ~a = [0, 1, {\color{red}{3}}, 4, 2]~, ~b = [0, 1, 4, {\color{red}{3}}, 2]~

  • ~a = [2, 1, {\color{red}{3}}, 4, 0]~, ~b = [2, 1, 4, {\color{red}{3}}, 0]~

• Với ~k = 4~, đáp án là ~3~. Dưới đây là các cặp dãy ~a~ và ~b~ cho ra cùng ma trận MEX nhưng vị trí của giá trị ~4~ khác nhau:

  • ~a = [0, 1, 3, {\color{red}{4}}, 2]~, ~b = [0, 1, {\color{red}{4}}, 3, 2]~

  • ~a = [2, 1, 3, {\color{red}{4}}, 0]~, ~b = [2, 1, {\color{red}{4}}, 3, 0]~

  • ~a = [3, 1, 2, {\color{red}{4}}, 0]~, ~b = [3, 1, {\color{red}{4}}, 2, 0]~

Cho một bảng kích thước ~n \times m~. Ban đầu, tất cả các ô trên bảng đều có giá trị bằng ~0~. Ta có thể thực hiện các thao tác sau:

• Đặt một viên gạch hình chữ nhật kích thước ~1 \times k~ (ngang) hoặc ~k \times 1~ (dọc), với ~k~ là số nguyên dương bất kỳ, lên trên bảng.

Mỗi lần đặt một viên gạch, giá trị của tất cả các ô mà viên gạch che phủ sẽ tăng lên đúng ~1~.

Hãy xác định số lượng viên gạch ít nhất cần đặt sao cho sau cùng, giá trị tại mỗi ô ~(i,j)~ trên bảng đúng bằng ~a_{i,j}~.

Input

Mỗi bộ dữ liệu gồm nhiều test case. Dòng đầu tiên chứa số lượng test case ~t~ (~1 \le t \le 1000~). Phần mô tả các test case như sau.

Dòng đầu tiên của mỗi test case là hai số nguyên dương ~n~ và ~m~ (~1 \le n, m \le 50~).

Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa ~m~ số nguyên ~a_{i, 1}, a_{i, 2}, \dots, a_{i, m}~ (~0 \le a_{i, j} \le 10^9~).

Đảm bảo rằng tổng của ~nm~ ở mỗi bộ test không vượt quá ~3000~.

Output

Với mỗi test case, in ra một số nguyên duy nhất là số viên gạch ít nhất cần đặt.

Scoring

Sample Input 1

3
1 4
1 0 3 2
3 3
0 1 0
1 1 1
0 1 0
3 3
0 1 0
1 2 1
0 1 0

Sample Output 1

4
3
2