Cho một xâu ~s~ gồm các kí tự thường, in hoa và khoảng cách. Bạn được yêu cầu phải định dạng thành chuỗi ~f(s)~ bằng cách xoá tất cả các kí tự khoảng cách. Và với mỗi từ, bạn phải in hoa chữ cái đầu tiên.

Ví dụ: ~s =~ "hello bedao" thì ~f(s) =~"HelloBedao"

Input

• Một dòng duy nhất bao gồm xâu ~s~ ~(0 < |s| \le 10^6)~.

Output

• Một dòng duy nhất là kết quả của ~f(s)~.

Sample Input 1

hello bedao

Sample Output 1

HelloBedao

Cuốn theo cơn sốt bing chilling những ngày gần đây, trong khu phố bé Quân ở đã mở thêm rất nhiều quán bán bing chilling để đáp ứng nhu cầu đu trend của giới trẻ.

Để thu hút khách hàng, các quán bing chilling đưa ra mức khuyến mãi vô cùng hấp dẫn như sau: "Năm nghìn một bing chilling, mười nghìn hai bing chilling năm nghìn". Ngoài ra, quán thứ ~i~ sẽ tặng thêm cứ mỗi ~y_i~ bing chilling khi khách hàng mua ~x_i~ bing chilling.

Bé Quân là một fan cuồng của bing chilling, trước mức khuyến mãi vô cùng hấp dẫn đó, quân quyết định sẽ ăn thử hết tất cả các quán ở đây. Ở quán bing chilling thứ ~i~, cậu muốn ăn ~a_i~ que, hỏi số tiền ít nhất cậu cần bỏ ra là bao nhiêu.

Input

• Dòng đầu tiên chứa một số nguyên ~t~ là số tiệm bing chilling mới mở trong phố bé Quân ~(1 \leq t \leq 10^5)~.

• ~t~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên dương ~x_i, y_i, a_i~ là khuyến mãi của quán thứ ~i~ và số lượng bing chilling Quân muốn ăn ở quán này ~(1 \leq x_i, y_i \leq 1000, 1 \leq a_i \leq 10^5)~.

Output

• Gồm ~t~ dòng, dòng thứ ~i~ là số tiền ít nhất bé Quân cần bỏ ra để ăn đủ số bing chilling cậu muốn ở quán thứ ~i~ (tính theo đơn vị nghìn đồng).

Subtask

• ~30\%~ số test có ~t \leq 20~

• ~70\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

1
2 2 5

Sample Output 1

15

Sample Input 2

3
1 1 9
4 3 16
7 5 23

Sample Output 2

25
50
70

Bé Đào là một người yêu thích sự sạch sẽ, ngăn nắp, nên đã quyết định chi tiền ra mua một con robot hút bụi đắt tiền về để giúp mình dọn dẹp nhà cửa.

Sàn nhà Bé Đào có thể mô tả như một mẳng phẳng hai chiều. Tại mỗi lượt di chuyển, từ vị trí ~(x, y)~ trên sàn nhà, robot có thể di chuyển sang trái đến ô ~(x, y-1)~, ~(x, y+1)~, ~(x+1, y)~ hoặc ~(x-1, y)~ tương ứng với bốn hướng trái, phải, lên, xuống.

Khi mới mua về, hành trình của robot được mặc định là một xâu kí tự độ dài ~n~ chỉ gồm bốn kí tự ~L~, ~R~, ~U~, ~D~ mô tả bốn hướng di chuyển. Bé Đào muốn nhà lúc nào cũng ngăn nắp cho nên Bé muốn thay đổi một số kí tự của hành trình sao cho sau khi dọn dẹp xong nhà, robot quay về đúng vị trí bắt đầu.

Tính số kí tự nhỏ nhất Bé cần thay đổi.

Input

• Dòng đầu tiên chứa một số nguyên ~n~ là độ dài của hành trình của robot ~(1 \leq n \leq 10^5)~.

• Dòng thứ hai chứa một xâu kí tự độ dài ~n~ chỉ chứa các kí tự ~L~, ~R~, ~U~, ~D~ mô tả hành trình ban đầu của robot.

Output

• Một số nguyên duy nhất là số lượng kí tự nhỏ nhất Bé Đào cần thay đổi.

• In ra ~-1~ nếu không tồn tại phương án thực hiện.

Subtask

• ~20\%~ số test có ~n \leq 20~.

• ~40\%~ số test khác có ~n \leq 5000~.

• ~40\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

4
LLUD

Sample Output 1

1

Sau trận thua của Argentina trước Saudi Arabia bao nhiêu tài sản của Tri_phan đã bị cuốn theo chiều gió .Thấy Tri_phan khóc lóc thảm thương thần chó Mbfibat đã hiện lên và cho Tri_phan một cơ hội làm lại cuộc đời. Cụ thể thần giao cho một bài toán và bắt anh phải làm, chỉ cần giải xong là Tri_phan đã có thể có đủ tiền về bờ nhưng khổ là anh lại đang vùi đầu trong đống deadline T^T . Bạn hãy giúp Tri_phan giải bài toán trên nhé.

Bài toán như sau :

Bạn có một dãy ~a~ gồm ~N~ phần tử .

Có hai thao tác được biến đổi được sử dụng vô số lần:

+ Bạn chọn ~1~ vị trí ~i~ bất kỳ sao cho ~(1 \le i \le N)~ , bạn được đổi giá trị ~a[i]~ thành giá trị bất kỳ.

+ Dịch phải toàn bộ dãy ~a~ từ dãy ~a[1] , a[2] , ... , a[N]~ thành ~a[N] , a[1] , a[2] , ... , a[N - 1]~.

Có ~q~ truy vấn mỗi truy vấn có dạng ~x , b~ ~(1 \le x \le N , 1 \le b \le 10^{9})~ , bạn cần đổi giá trị ~a[x] = b~ và đếm số thao tác tối thiểu để đưa dãy về dãy có dạng ~1 , 2 , 3, ... , N~ (lưu ý giá trị ~a[x]~ thay đổi theo từng truy vấn).

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(1\le N \le 10^{5})~.

• Dòng thứ hai chứa ~N~ số nguyên ~a[i]~ cách nhau bởi dấu cách ~(1 \le i \le N , 1 \le a[i] \le 10^{9})~.

• Dòng thứ ba chứa ~q~ là số truy vấn ~(1\le q \le 10^{5})~.

• q dòng tiếp theo mỗi dòng chứa hai số nguyên dương cách nhau bởi dấu cách là ~x~ và ~b~ ~(1 \le x \le N , 1 \le b \le 10^{9})~

Output

• Với mỗi truy vấn ta in ra số thao tác tối thiểu nằm trên từng dòng một.

Subtask

• ~20\%~ số test có ~N\le 100, 1\le q \le 1000~.

• ~30\%~ số test có ~N\le 5000, 1\le q \le 5000~.

• ~50\%~ số test còn lại không có điều kiện gì thêm.

Sample Input 1

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

Sample Output 1

0
1
2
2
1

Notes

Vì Alice đang rất bận nên Alice sẽ đố nhanh Bob một bài toán khá dễ thôi.

Cho một mảng ~a~ gồm ~n~ phần tử nguyên dương, hãy tìm ra ~2~ dãy con liên tiếp (có thể rỗng) của dãy ~a~ sao cho nếu ta gộp ~2~ dãy lại thì ta được một dãy mới có các phần tử phân biệt, đồng thời có nhiều phần tử nhất.

Input

• Dòng đầu tiên nhập ~T~ ~(1 \le T \le 10)~ - số lượng bộ câu hỏi của Alice.

• Nhóm dòng thứ ~i~ trong ~T~ nhóm dòng tiếp theo sẽ có dạng:

  • Dòng đầu tiên gồm một số nguyên dương ~n~.

  • Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~.

Output

• In ra ~T~ dòng, trong đó dòng thứ ~i~ là độ dài lớn nhất hai dãy con tìm được của hỏi thứ ~i~.

Subtask

Gọi ~N~ là tổng các ~n~ trong tất cả các bộ câu hỏi.

• ~20\%~ số test có ~1 \le a_i, N \le 200~.

• ~40\%~ số test khác có ~1 \le a_i \le 20~ và ~1 \le N \le 10^6~.

• ~40\%~ số test còn lại có ~1 \le a_i \le 10^5~ và ~1 \le N \le 5000~.

Sample Input 1

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

Sample Output 1

3
4