Một chuỗi kết quả tung đồng xu ~P~ chỉ gồm các ký tự S và N. Gọi ~a~ là số ký tự S và ~b~ là số ký tự N trong ~P~. Hãy biểu diễn tỉ lệ ~a : b~ dưới dạng phân số tối giản.

Input

• Dòng đầu chứa số nguyên ~T~ là số bộ dữ liệu.
• ~T~ dòng tiếp theo, mỗi dòng chứa một chuỗi ~P~ gồm các ký tự S và N.

Output

Với mỗi chuỗi, in trên một dòng phân số tối giản dạng x/y, trong đó ~x = a/g~, ~y = b/g~ với ~g = \gcd(a, b)~.

Giới hạn

• Mỗi chuỗi ~P~ chứa ít nhất một ký tự S và ít nhất một ký tự N (~a, b \ge 1~).

Vào/ra bằng file

• Dữ liệu vào: đọc từ file COINLK.INP.
• Kết quả: ghi ra file COINLK.OUT.

Cho hai số nguyên ~L~ và ~R~. Hãy đếm số lượng số nguyên ~x~ thỏa mãn ~L \le x \le R~ và ~x~ có đúng 3 ước dương.

Input

Một dòng chứa hai số nguyên ~L~ và ~R~.

Output

Một số nguyên duy nhất là số lượng số có đúng 3 ước trong đoạn ~[L, R]~.

Giới hạn

• ~1 \le L \le R \le 10^{14}~

Vào/ra bằng file

• Dữ liệu vào: đọc từ file NUMBER.INP.
• Kết quả: ghi ra file NUMBER.OUT.

Có ~n~ địa điểm, địa điểm thứ ~i~ nằm ở tọa độ ~d_i~ trên một trục số. Có ~Q~ truy vấn, mỗi truy vấn cho hai địa điểm ~x~ và ~y~. Cần chọn một địa điểm ~z~ sao cho ~\max(|d_z - d_x|, |d_z - d_y|)~ nhỏ nhất.

Input

• Dòng đầu chứa hai số nguyên ~n~ và ~Q~.
• Dòng thứ hai chứa ~n~ số nguyên ~d_1, d_2, \ldots, d_n~ (không đảm bảo tăng dần).
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x, y~ (~1 \le x, y \le n~).

Output

Với mỗi truy vấn, in trên một dòng giá trị nhỏ nhất của ~\max(|d_z - d_x|, |d_z - d_y|)~.

Vào/ra bằng file

• Dữ liệu vào: đọc từ file TRAVEL.INP.
• Kết quả: ghi ra file TRAVEL.OUT.

Cho chuỗi ~A~ gồm ~N~ chữ cái. Chuỗi có thể được nén theo quy tắc: nếu một đoạn gồm ~D~ lần lặp liên tiếp của chuỗi ~S~ (~D \ge 2~) thì có thể viết thành D(S), trong đó ~S~ cũng có thể đã được nén. Các phần nén có thể ghép nối tiếp nhau.

Ví dụ: aaaa có thể nén thành 4(a).

Hãy tìm cách nén có độ dài ngắn nhất. Nếu có nhiều cách, chọn chuỗi có thứ tự từ điển nhỏ nhất (theo mã ASCII, nên ( < ) < chữ số < chữ cái).

Input

• Dòng đầu chứa số nguyên ~N~.
• Dòng thứ hai chứa chuỗi ~A~ độ dài ~N~.

Output

Một dòng duy nhất là chuỗi nén tìm được.

Giới hạn

• ~1 \le N \le 200~

Vào/ra bằng file

• Dữ liệu vào: đọc từ file WSTRING.INP.
• Kết quả: ghi ra file WSTRING.OUT.