Hệ thống bảo mật của trường Đại học Công nghệ Thông tin và Truyền thông (ICTU) thực hiện rút gọn các xâu ký tự để tạo chữ ký điện tử. Quy tắc rất đơn giản: Nếu có 2 ký tự giống nhau nằm kề nhau, chúng sẽ tự động triệt tiêu và biến mất khỏi xâu, các ký tự hai bên sẽ dồn lại. Quá trình này diễn ra liên tục cho đến khi không còn 2 ký tự giống nhau nào đứng cạnh nhau nữa. Hãy in ra xâu ký tự cuối cùng. Dữ liệu đảm bảo xâu cuối cùng không rỗng.

Input: Một xâu S chỉ gồm chữ cái in thường (Độ dài <= 10^5).

Output: Xâu sau khi rút gọn.

Ví dụ:

Input:

abbaca

Output:

ca

(Giải thích: bb biến mất -> aaca. Sau đó aa biến mất -> ca).

Có N thí sinh tham gia kỳ thi lập trình, thí sinh i có điểm đánh giá năng lực là A_i. Để đảm bảo tính cạnh tranh đồng đều, giám khảo muốn chia N thí sinh này vào các phòng thi sao cho: chênh lệch điểm số giữa người giỏi nhất và người kém nhất trong cùng MỘT phòng thi không được vượt quá K. Mỗi phòng có thể chứa bao nhiêu người tùy ý. Hãy tính số lượng phòng thi ít nhất cần sử dụng.

Input:

Dòng 1: N, K (1 <= N <= 10^5, 0 <= K <= 10^9).

Dòng 2: N số nguyên Ai (0 <= Ai <= 10^9).

Output: Số lượng phòng thi ít nhất.

Ví dụ:

Input:

5 2
1 5 2 4 6

Output:

2

(Giải thích: Xếp (1, 2) vào phòng 1 (chênh lệch 1 <= 2). Xếp (4, 5, 6) vào phòng 2 (chênh lệch 2 <= 2). Cần 2 phòng).

Hai số nguyên dương được coi là một "cặp đôi hoàn hảo" nếu cả hai đều là số nguyên tố và chúng có tổng các chữ số bằng nhau. Cho một mảng gồm N số nguyên dương phân biệt, hãy đếm xem trong mảng này có bao nhiêu cặp đôi hoàn hảo (không phân biệt thứ tự cặp).

Input:

Dòng 1: N (1 <= N <= 10^5).

Dòng 2: N số nguyên dương Ai (1 <= Ai <= 10^6).

Output: Số lượng cặp đôi hoàn hảo.

Ví dụ:

Input:

5
11 2 23 5 41

Output:

4

Đôi khi một số từ như "localization" hoặc "internationalization" quá dài đến nỗi việc viết chúng nhiều lần trong một văn bản khá mệt mỏi. Hãy xem xét một từ quá dài, nếu độ dài của nó dài hơn 10 ký tự. Tất cả các từ quá dài nên được thay thế bằng một từ viết tắt đặc biệt. Chữ viết tắt này được thực hiện như thế này: chúng tôi viết ra chữ cái đầu tiên và chữ cái cuối cùng của một từ và giữa chúng tôi viết số lượng chữ cái giữa chữ cái đầu tiên và chữ cái cuối cùng. Con số đó nằm trong hệ thập phân và không chứa bất kỳ số 0 đứng đầu nào. Do đó, "localization" sẽ được đánh vần là "l10n" và "internationalization" sẽ được đánh vần là "i18n".

Bạn được đề nghị tự động hóa quá trình thay đổi các từ bằng chữ viết tắt. Tại đó, tất cả các từ quá dài nên được thay thế bằng chữ viết tắt và các từ không quá dài sẽ không trải qua bất kỳ thay đổi nào.

Đầu vào:

• Dòng đầu tiên chứa một số nguyên n (1<=n<=100). Mỗi n dòng sau chứa một từ.
• Tất cả các từ bao gồm các chữ cái Latinh viết thường và có độ dài từ 1 đến 100 ký tự.

Đầu ra: In n dòng. Dòng thứ i phải chứa kết quả thay thế từ thứ i từ dữ liệu đầu vào.

Input:

4
word
localization
internationalization
pneumonoultramicroscopicsilicovolcanoconiosis

Output:

word
l10n
i18n
p43s