Kinich ngủ dậy và nhận được một hộp quà bất ngờ ở trên điện thoại của mình. Anh ấy quyết định mở nó ra và phát hiện nó là một trò chơi. Người chơi được cho một mảng ~a~ có ~N~ phần từ và bắt đầu với ~0~ điểm.

Một vòng chơi sẽ được thực hiện như sau:

• Chọn 2 phần từ ~a_i~ và ~a_j~ trong đó ~i~ và ~j~ chưa được chọn lần nào trước đó, và ~a_i = a_j~. Hành động này cho người chơi ~1~ điểm

Là một gamer, Kinich muốn phải tối đa điểm cho trò chơi này nên đã chơi nó rất nhiều lần. Cho ~T~ lần chơi của Kinich, hãy in ra số điểm lớn nhất mà Kinich có thể đạt được sau mỗi lần chơi.

Input

Dòng đầu tiên chứa số nguyên ~T~: số test case / số lần Kinich đã chơi

Dòng đầu tiên của mỗi test case chứa số nguyên ~N~: kích thước của mảng ~a~ trong trò chơi

~N~ số tiếp theo: các phần từ của mảng ~a~

Output

In ra ~T~ dòng, dòng thứ ~i~ là số điểm tối đa Kinich có thể đạt được trong lần chơi thứ ~i~

Giới hạn

~1 <= T <= 1000~

~1 <= N <= 1000~

Test mẫu

Input

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

Output

0
1
0
1
3

Citlali đang muốn tổ chức một bữa tiệc ở nhà mình, bà đã chuẩn bị rất nhiều đồ ngọt cho các vị khách của mình. Nhưng khổ nỗi, bà lại quên không chia phần các miếng bánh của mình.

Vì quá lười và chỉ muốn nằm ngủ, nên bà đã ép Aether giúp mình chia chúng. Aether cũng đang rất bối rối không biết phải làm như nào, nên anh đã gọi cho bạn để cầu cứu.

Citlali có ~N~ miếng bánh, kích thước của từng miếng bánh là ~a_i~ và kích thước của chúng là lớn dần. Bạn được nhờ chia số bánh này ra thành ~K~ phần liên tiếp, với chi phí chia cho một phần ~a_l~ đến ~a_r~ là ~max(a_{l..r}) - min(a_{l..r})~.

Citlali muốn số tiền bà mất là ít nhất (bà làm gì có tiền), nên bạn cần tính giá trị này

Input

Dòng đầu tiên chứa 2 số nguyên ~N~ và ~K~: số miếng bánh và số phần bánh phải chia

Dòng thứ 2 chứa ~N~ số nguyên: kích thước của ~N~ miếng bảnh

Output

In ra kết quả của bài toán: chi phí chia bánh ít nhất.

Giới hạn

~1 <= K <= N <= 3*10^5~ ~1 <= a_i <= 10^9~

Test mẫu

Input

6 3
4 8 15 16 23 42

Output

12

Mualani rất thích đi lướt sóng trên chiêc ván cá mập của cô ấy. Vì thế hôm nay, cô quyết định rủ bạn tham gia lướt sóng ở phía Nam Natlan.

Chặng lướt sóng mà Mualani dẫn bạn tới có thể được biểu diễn bới một đường thẳng. Mualani sẽ bắt đầu từ vị trí 1 và chặng sẽ kết thúc ở vị trí ~L~.

Khi Mualani đang ở vị trí ~x~ và có sức nhảy ~k~, cô có thể nhảy từ vị trí ~x~ đến bất kỳ vị trí nào trong khoảng ~[x,x+k]~. Ban đầu, cô có sức nhảy là ~1~.

Chặng lướt này không bằng phẳng, có ~N~ chướng ngại vật ở trên chặng, mỗi chướng ngại vật được mô tả bởi một khoảng ~[l, r]~

Trên chặng còn có ~M~ bình tăng sức mạnh, bình tăng sức mạnh thứ ~i~ ở vị trí ~x_i~ có giá trị ~v_i~. Khi Mualani gặp chúng, cô có lựa chọn là uống bình tăng sức mạnh để tăng sức nháy thêm một lượng ~v_i~ hoặc bỏ qua chúng. Có thể nhiều bình tại cùng một vị trí nhưng không có bình nào ở trong vùng chướng ngại vật.

Vậy Mualani cần nhặt ít nhất bao nhiêu bình để có thể hoàn thành được chặng lướt sóng này?

Input

Dòng đầu tiên chưa một số nguyên ~T~: số test case

Dòng đầu tiên của test case chứa 3 số nguyên: ~N~, ~M~, ~L~: số chướng ngại vật, số bình tăng sức mạnh và độ dài chặng

~N~ dòng tiếp theo, mỗi dòng chứa 2 số nguyên ~l_i~ và ~r_i~, mô tả chướng ngại vật thứ ~i~

~M~ dòng tiếp theo, mỗi dòng chứa 2 số nguyên ~x_i~ và ~v_i~, mô tả bình tăng sức mạnh thứ ~i~.

Output

In ra ~T~ dòng là kết quả của từng bộ test, nếu Mualani không thể hoàn thành chặng, in ra ~-1~.

Giới hạn

~1 <= T <= 10^4~

~1 <= N,M <= 2*10^5~

~3 <= L <= 10^9~

~1 <= x_i <= 10^9~, bình tăng sức mạnh nằm ở ô không có chướng ngại vật

~1 <= v_i <= 10^9~

Đảm bảo giới hạn của N và M trong các test case không quá ~2*10^5~

Test mẫu

Input

2
2 5 50
7 14
30 40
2 2
3 1
3 5
18 2
22 32
4 3 50
4 6
15 18
20 26
34 38
1 2
8 2
10 2

Output

4
-1

Mavuika, hay Hỏa Thần, là người cai trị vùng đát Natlan. Gần đây, xuất hiện các dấu vết của Abyss Order tới để đánh chiểm vùng đất này. Vì thể, để bảo vệ cho người dân, cô yêu cầu Xilonen chế tạo ra các khiên bảo vệ cho các thành phố.

Vùng đất Natlan có thể được biểu diễn trên trục tọa độ, với ~N~ thành phố, thành phố thứ ~i~ ở vị trí thứ ~x_i~. Xilonen đặt ra ~M~ trụ phát khiên bảo vệ, trụ thứ ~j~ ở vị trí thứ ~y_j~.

Tất cả trụ bảo vệ có tầm phủ bảo vệ là ~r~, có nghĩa là nếu trụ bảo vệ được đặt ở vị trí ~i~ thì trụ đó sẽ bảo vệ được các thành phố nằm trong khoảng từ ~[i-r,i+r]~.

Xilonen đặt ra cho bạn một thử thách, tìm ra tầm phủ bảo vệ ~r~ thấp nhất mà các trụ vẫn có thể bảo vệ tất cả các thành phố có trong Natlan

Input

Dòng đầu tiên chứa 2 số nguyên ~N~ và ~M~: số thành phố trong Natlan và số trụ bảo vệ

Dòng thứ hai chứa ~N~ số nguyên: vị trí của các thành phố trong Natlan theo thứ tự tăng dần

Dòng thứ ba chứa ~M~ số nguyến: vị trí của các trụ bảo vệ Xilonen đã đặt theo thứ tự tăng dần

Output

In ra ~r~ là tầm phủ nhỏ nhất có thể của trụ bảo vệ

Giới hạn

~1 <= N, M <= 10^5~ ~-10^9 <= x_i, y_i <= 10^9~

Test mẫu

Input

3 2
-2 2 4
-3 0

Output

4

Có ~N~ tòa nhà chọc trời ở Hà Nội, mỗi tòa nhà có chiều cao của tòa nhà thứ ~i~ là ~h_i~. Hôm nay, tiến sĩ Heinz Doofenshmirtz tự nhiên lại nổi hứng muốn chiếm thành phố Hà Nội, nên ông đã tạo cỗ máy động đất nhằm phá hủy các căn nhà ở đây. Cỗ máy đã bắn ~N-1~ căn nhà đầu tiên, chỉ còn tòa thứ ~N~ đang an toàn. Bạn là một đặc vụ của OWCA xuất phát từ tòa nhà thứ nhất, cần phải đến căn nhà thứ ~N~ để đảm bảo an toàn có thể thực hiện một cú nhảy từ tòa nhà thứ ~i~ đến tòa nhà thứ ~j~ (~i < j~) nếu thỏa mãn một trong các điều kiện sau:

• ~i + 1 = j~
• ~max(h_{i+1}, ..., h_{j-1}) < min(h_i, h_j)~
• ~max(h_i, h_j) < min(h_{i+1}, ..., h_{j-1})~

Hãy tính toán xem bạn cần ít nhất bao nhiêu bước nhảy để đảm bảo an toàn.

Input

Dòng đầu tiên chứa một số nguyên ~N~: số tòa nhà chọc trời ở Hà Nội

Dòng thứ hai chứa ~N~ số nguyên ~h_1, h_2,...,h_n~: chiều cao của tòa nhà thứ ~i~.

Output

In ra một số nguyên ~m~ là số lần nháy ít nhất mà bạn cần nhảy.

Giới hạn

~2 <= N <= 3*10^5~

~1 <= h_i <= 10^9~

Test mẫu

Input

5
1 3 1 4 5

Output

3