Nhân thích học toán. Đương nhiên là Nhân cũng thích nhân. Đối với Nhân, mọi thứ đều có thể biểu diễn được dưới dạng những con số. Hôm nay, Nhân đã gặp phải \(n\) sự vật sự việc khác nhau và cậu đã ghi vào nhật kí của mình một dãy \(a\) gồm \(n\) số tượng trưng cho những thứ ấy.
Để đánh giá mỗi ngày trôi qua tốt hay xấu, Nhân sẽ dựa vào một con số. Số này được tính bằng: Nhân sẽ nhân toàn bộ \(n\) số của ngày hôm đó lại. Nếu tích này vượt quá \(10^{18}\), Nhân sẽ coi như con số đó là \(-1\).
Tuy nhiên khá xui là Nhân đã bỏ quên máy tính ở trường nên không thể nhân được! Bạn hãy nhân giúp Nhân số trên (cho ngày hôm nay) nhé.

Input

• Dòng đầu tiên chứa \(n\) \((2 \le n \le 10^5)\): độ dài dãy
• Dòng tiếp theo chứa \(n\) số nguyên không âm \(a_1, a_2, a_3, \dots, a_n (0 \le a_i \le 10^{18})\)

Output

• Dòng duy nhất chứa tích theo mô tả của đề bài

2
1000000000 1000000000

1000000000000000000

3
999999000001 9901 101

-1

Vì quá mệt khi phải tìm ý tưởng để viết cốt truyện cho đề ôn Tin học trẻ lần này, Quý quyết định chọn 1 bài tập ngẫu nhiên để làm giải trí. Bài tập mà Quý chọn có đề bài như sau:

Cho \(1\) dãy \(A\) gồm \(n\) số nguyên dương và \(1\) số \(e\). Hãy đếm số cặp \((i,k)\) thỏa mãn các điều kiện sau:

• \(1 \le i, k\)
• \(i + e \times k \le n\)
• Tích \(a_i \times a_{i + e} \times a_{i + 2e} \times ... \times a_{i + ke}\) là 1 số nguyên tố

Nhắc lại, số nguyên tố là số lớn hơn \(1\) và chỉ có \(2\) ước dương là \(1\) và chính nó.

Tuy nhiên, Quý đã không còn đủ sức để làm được bài này nên muốn nhờ các bạn hãy thay Quý giải bài tập trên.

Input

• Dòng đầu tiên gồm số nguyên \(t\) (\(t \le 10\)) là số lượng test cases của bài toán.

Mỗi test có cấu trúc như sau:

• Dòng đầu tiên bao gồm \(2\) số nguyên dương \(n\) và \(e\) (\(1 \le e \le n \le 10^5\)) là kích thước của mảng \(A\) và số \(e\) đề bài cho.
• Dòng thứ \(2\) bao gồm \(n\) số nguyên dương \(a_1, a_2, a_3, ..., a_n\) \((a_i \le 10^6)\)

Output

• Với mỗi test, in ra \(1\) số nguyên là số lượng cặp (\(i\), \(k\)) thỏa mãn điều kiện đề bài trên một dòng.
• In ra tổng cộng \(t\) dòng cho \(t\) test.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n, e \le 200, a_i \le 10^3\)
• Subtask \(2\) (\(30\%\) số điểm): \(e = 1, n \le 10^5, a_i \le 10^3\)
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm

6
7 3
10 2 1 3 1 19 3
3 2
1 13 1
9 3
2 4 2 1 1 1 1 4 2
3 1
1 1 1
4 1
1 2 1 1
2 2
1 2

2
0
4
0
5
0

(Ở một tương lai xa xôi) Trên con đường mới được quy hoạch của thành phố X, có \(n\) tòa nhà cao tầng nằm trên một con đường (tạm coi như một đường thẳng). Nhà thứ \(i\) có độ cao là \(h_i\) mét.
Việt không thích những tòa nhà có cùng độ cao nằm gần nhau. Cậu định nghĩa một dãy nhà \([l,r] (l\le r)\) là "nhàm chán" nếu như trong toàn bộ những căn nhà thứ \(l,l+1,l+2,\dots,r-1,r\) chỉ có không quá \(k\) độ cao khác nhau.
Nhằm đánh giá con đường này, Việt cần tính số lượng dãy nhà nhàm chán. Vì đã thấm mệt sau khi đi từ đầu đường tới cuối đường để lấy thông tin về chiều cao của các tòa nhà, Việt nhờ bạn lập trình giải quyết vấn đề trên. Hãy giúp Việt nhé!
Bonus: sau khi hỏi thị trưởng, Việt đã có được một số thông tin giúp việc tính toán trở nên dễ dàng hơn. Thông tin này được kí hiệu bởi số \(\theta\)

Input

• Dòng đầu tiên chứa \(\theta\) \((\theta \in \{1,2,3,4,5\})\): thông tin mới có được từ thị trưởng
• Dòng thứ hai chứa \(n,k\) \((1 \le n,k \le 10^5)\): số tòa nhà, và số định nghĩa sự "nhàm chán"
• Dòng tiếp theo chứa \(n\) số nguyên dương \(h_1, h_2, h_3, \dots, h_n (1 \le h_i \le 10^9)\)

Output

• Dòng duy nhất chứa số dãy nhà nhàm chán mà bạn đếm được

Scoring

• Subtask 1 (\(20\%\) số điểm): \(\theta = 1, h_i \le n \le 100\)
• Subtask 2 (\(30\%\) số điểm): \(\theta = 2, h_i \le n \le 1000\)
• Subtask 3 (\(15\%\) số điểm): \(\theta = 3\) và các tòa nhà có chiều cao khác nhau đôi một.
• Subtask 4 (\(15\%\) số điểm): \(\theta = 4, k = 1\)
• Subtask 5 (\(20\%\) số điểm): \(\theta = 5\), không có ràng buộc gì thêm.

1
5 2
1 2 3 1 1

10

Trải qua quá nhiều năm thăng trầm trong đầu tư chứng khoán, Nam đã trở thành một bậc thầy đầu tư. Hơn cả thế, Nam còn có năng lực dự đoán tương lai và biết trước được giá cổ phiếu IVN sẽ lên xuống \(n\) lần trong hôm nay. Cụ thể, Nam biết trước nếu "vào lệnh" vào đợt thứ \(i\) thì sẽ đem lại lợi nhuận là \(a_i\) VNĐ. Nếu \(a_i\) âm nghĩa là Nam sẽ thua lỗ \(-a_i\) VNĐ khi vào lệnh ở đợt \(i\).
Tuy nhiên, vì đã quá giàu nên Nam không muốn tổng lợi nhuận là lớn nhất. Thay vào đó, Nam muốn độ "chất chơi" phải cao, tức là đặt lệnh vào càng nhiều đợt càng tốt, kể cả có những đợt âm rất nhiều tiền (và dù Nam đã biết trước điều đó!). Để không bị đánh giá là đầu tư thiếu thông minh, Nam muốn đảm bảo sau mỗi lần vào lệnh, tổng lợi nhuận thu được là không âm.
Là một trợ lý mới được tuyển dụng, bạn được Nam nhờ tính độ "chất chơi".

Input

• Dòng đầu tiên chứa \(n\) \((1 \le n \le 2.10^5)\): số đợt thay đổi của cổ phiếu
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n (-10^9 \le a_i \le 10^9)\): nếu Nam vào lệnh ở đợt thứ \(i\) thì tổng lợi nhuận tăng lên \(a_i\).

Output

• Dòng duy nhất chứa số lần vào lệnh nhiều nhất có thể, thỏa mãn yêu cầu trên.

Scoring

• Subtask 1 (\(40\%\) số điểm): \(1 \le n \le 20\)
• Subtask 2 (\(40\%\) số điểm): \(1 \le n \le 1000\)
• Subtask 3 (\(20\%\) số điểm): Không có giới hạn thêm.

6
4 -4 1 -3 1 -3

5