Cho ~n~ bình nhiệt, các bình đôi một nối với nhau. Các bình có thể truyền nhiệt qua lại cho nhau. Nhiệt lượng của mỗi bình được tính bằng số lượng nhiệt truyền đi, trừ đi số nhiệt lượng nhận vào.

Cho biết nhiệt lượng của ~n - 1~ bình, từ bình ~1~ tới bình ~n - 1~. Tìm nhiệt lượng của bình thứ ~n~.

INPUT

Dòng đầu tiên chứa số nguyên dương ~t~ (~1 \le t \le 10^4~) là số test.

Dòng đầu tiên của mỗi test gồm số nguyên dương ~n~ (~1 \le n \le 100~) là số bình.

Dòng thứ hai của mỗi test gồm ~n - 1~ số nguyên dương ~a_1, a_2, ..., a_{n - 1}~ (~0 \le |a_i| \le 100~) là nhiệt lượng của từng bình.

OUTPUT

~t~ dòng, mỗi dòng là nhiệt lượng của bình thứ ~n~.

SAMPLE INPUT

2
3
1 2
3
1 -2

SAMPLE OUTPUT

-3
1

Một cửa hàng có các món hàng, các món hàng đều có giá là ~3~ đơn vị.

Cứ ba món hàng, ta có thể gói thành gói hàng cấp ~1~. Cứ ba gói hàng cấp ~1~, ta có thể gói thành gói hàng cấp ~2~, và tương tự như vậy.

Chi phí của một gói hàng cấp ~m~, bao gồm ~3^m~ món hàng lẻ, là ~3^{m + 1} + m \times 3^{m - 1}~ đơn vị.

Có ~t~ người muốn mua hàng, mỗi người muốn mua ~n~ món hàng, với tối đa ~k~ lần mua. Hãy đưa ra chi phí nhỏ nhất để mua ~n~ món hàng, sao cho số lần mua hàng không quá ~k~ lần.

INPUT

Dòng đầu tiên chứa số nguyên dương ~t~ (~1 \le t \le 4000~) là số người cần mua hàng.

~t~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~n~ và ~k~ (~1 \le n, k \le 10^9~).

OUTPUT

~t~ dòng, mỗi dòng là chi phí tối thiểu cho từng người. Nếu không tồn tại cách thỏa mãn, in ra ~-1~.

SAMPLE INPUT

2
3 2
10 2

SAMPLE OUTPUT

10
36

SUBTASKS

Cho ~n~ điểm trên trục Ox, điểm thứ ~i~ ở vị trí ~i~ trên trục Ox. Có một người đang đứng tại điểm ~0~.

Người này di chuyển theo quy tắc:

• Ở bước di chuyển đầu tiên, người này đứng ở điểm ~i~, cần di chuyển tới điểm ~j~ sao cho ~j > i~, và ~j - i~ là bội của ~k~.
• Ở bước di chuyển thứ hai, ~j - i~ phải là bội của ~k + 1~.
• ...
• Ở bước di chuyển thứ ~m~, ~j - i~ phải là bội của ~k + m - 1~.

Tính số cách đi của người đó từ điểm ~0~, đi đếm điểm ~i~, với mọi ~i~ từ ~1~ tới ~n~.

INPUT

Dòng duy nhất chứa hai số nguyên dương ~n~ và ~k~ (~1 \le n, k \le 2 \times 10^5~), là số điểm và số ~k~ trong đề bài.

OUTPUT

~n~ số nguyên dương, số thứ ~i~ là số cách di chuyển từ điểm ~0~ tới điểm ~i~.

Vì kết quả có thể rất lớn, hãy in ra phần dư của kết quả khi chia cho ~998244353~.

SAMPLE INPUT

5 1

SAMPLE OUTPUT

1 1 2 2 3

SUBTASKS

Trong một nhà sách có ~n~ giá sách, giá sách thứ ~i~ có ~a_i~ quyển sách. Người thủ thư có thể thực hiện một trong hai thao tác như sau:

• Chọn một cặp giá sách liên tiếp nhau, lấy đi một quyển sách ở cả hai giá sách (lưu ý, nếu giá sách thứ ~i~ hết sách, thì hai giá sách ~i - 1~ và ~i + 1~ cũng không phải cặp giá sách liên tiếp thỏa mãn). Số lần được thực hiện thao tác này là không giới hạn.
• Chọn một cặp giá sách liên tiếp nhau, và hoán đổi số sách của hai giá sách đó. Thao tác này được thực hiện tối đa một lần, và nếu thực hiện, chỉ được thực hiện ngay trước khi thực hiện thao tác ~1~ nói trên.

Yêu cầu: Xác định sau hai thao tác trên, có thể đạt trạng thái với tất cả giá sách đều không còn quyển sách nào hay không.

INPUT

Dòng đầu tiên chứa số nguyên dương ~t~ (~1 \le t \le 10^4~) là số test.

Dòng đầu tiên của mỗi bộ test gồm số nguyên dương ~n~ (~1 \le n \le 2 \times 10^5~) mô tả số giá sách.

Dòng thứ hai của mỗi bộ test gồm ~n~ số nguyên không âm ~a_i~ (~0 \le a_i \le 10^9~) mô tả số sách của từng giá sách.

Dữ liệu đảm bảo tổng ~n~ qua mọi test không vượt quá ~2 \times 10^5~.

OUTPUT

Với mỗi bộ test, in ra YES hoặc NO tương ứng với có thể hay không thể đạt trạng thái nói trên.

SAMPLE INPUT

2
4
1 1 2 2
4 
1 2 1 2

SAMPLE OUTPUT

YES
YES

SUBTASKS