Cho một danh sách gồm ~n~ tên riêng, mỗi tên riêng gồm một hoặc nhiều từ được tạo bởi các kí tựlatin. Giữa các từ có ít nhất một kí tự khoảng trắng, và có thể có kí tự khoảng trắng ở đầu hoặc cuối tên riêng. Nhiệm vụ của bạn là chuẩn hoá các tên riêng này về đúng định dạng.

Một tên riêng được gọi là đúng định dạng nếu thoả các điều kiện sau:

• Giữa các từ có đúng một kí tự khoảng trắng và không có kí tự khoảng trắng nào ở đầu hoặc cuối tên riêng.
• Với mỗi từ trong tên riêng, kí tự đầu tiên của từ được in hoa và các kí tự còn lại của từ được in thường.

Ví dụ:

• “Viet Nam”, “Ha Noi”, “Hue”, “Ho Chi Minh”, “Can Tho” là các tên riêng đúng định dạng.
• “viet nam”, “HA NOI”, “hUE”, “Ho Chi Minh”, “ Can Tho ” là các tên riêng chưa đúngđịnh dạng.

Input

• Dòng đầu tiên gồm số nguyên dương ~n (1 ≤ n ≤ 1000)~ - số tên riêng trong danh sách
• ~n~ dòng tiếp theo, mỗi dòng gồm một xâu chứa không quá 50 kí tự - mô tả một tên riêng.

Output

• In ra các tên riêng sau khi đã được chuẩn hoá, mỗi tên riêng nằm trên một dòng.

Sample

Input #1

6
viet nam
HA NOI
hUE
Ho Chi Minh
Can Tho
Free Contest

Output #1

Viet Nam
Ha Noi
Hue
Ho Chi Minh
Can Tho
Free Contest

Problem source: Kc97ble - Free Contest