Vũ công là những người đứng sau sự thành công của mỗi tiết mục biểu diễn nên đội ngũ quản lí của Jisoo đã kí hợp đồng với ~n~ vũ công với kĩ năng nhảy múa vô cùng điệu nghệ, được đánh số từ ~1~ đến ~n~. Diễn viên thứ ~i~ có chiều cao là ~h_i~ (~h_i \le 10~). Jisoo muốn chọn ra các vũ công liên tiếp có chỉ số từ ~l~ đến ~r~ để hỗ trợ cho các tiết mục của mình. Một nhóm gồm ~x~ vũ công được gọi là “sáng giá” nếu khi họ xếp hàng theo thứ tự chiều cao tăng dần, chiều cao của người thứ ~\lfloor \frac{x+1}{2} \rfloor = \lceil \frac{x+1}{2} \rceil~. Lúc này Jisoo muốn biết có bao nhiêu cách chọn ra một nhóm “sáng giá”, nhưng vì số lượng vũ công ứng tuyển quá lớn nên bạn hãy tính giúp Jisoo nhé.

Yêu cầu: Tính số lượng nhóm "sáng giá" có thể chọn được.

Input

• Dòng đầu tiên gồm số nguyên ~T~ là số lượng testcase (~1 \le T \le 5~);
• Mỗi testcase gồm 2 dòng, dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 10^5~). Dòng thứ hai gồm ~n~ số nguyên dương ~h_1, h_2, \dots, h_{n-1}, h_n~ (~1 \le h_i \le 10~).

Output

• Với mỗi testcase, in ra một dòng duy nhất là đáp án của bài toán.