Hiếu đi dự đám cưới ở một nhà hàng trong thành phố. Trời nắng nên con đường hành lang đi từ nhà hàng ra bãi giữ xe được che bởi các tấm bạt có kích thước khác nhau (đường hành lang là đường thẳng). Nhưng vì các chú bảo vệ lo nhận và giữ xe nên che các tấm bạt rất lộn xộn chỗ thì khít, chỗ thì chồng lên nhau, chỗ thì hở ra. Hiếu muốn tìm đoạn đường dài nhất trên đường mình đi được che kín bởi các tấm bạt.

Cho \(n\) cặp số \([l_{i},r_{i}]\) là vị trí đầu và vị trí cuối của mỗi tấm bạt theo chiều dài hành lang.

Yêu cầu: Viết chương trình tìm độ dài lớn nhất của đoạn đường được che kín bởi các tấm bạt.

Input

• Dòng đầu chứa một số nguyên \(n\) \((1 < n \leq 10000)\) là số lượng tấm bạt.
• \(n\) dòng tiếp theo, mỗi dòng biểu diễn vị trí của mỗi tấm bạt theo chiều dài hành lang là \(l_i\) và \(r_i\) \((0 \leq l_{i}, r_{i} \leq 60000)\).

Output

• Ghi ra một số nguyên duy nhất theo yêu cầu trên.

Example

7
7 12
0 5
20 25
33 38
6 8
27 34
11 19

13

Từ một số nguyên dương \(k\) ban đầu, ta thực hiện biến đổi số \(k\) theo quy tắc biến đổi sau đây:

Nếu \(k\) chia hết cho \(6\) thì thay số \(k\) bởi thương \(k:6\); còn nếu \(k\) không chia hết cho \(6\) thì thay số \(k\) bởi tích \(3 \times k\).

Yêu cầu: Hãy xác định số lần biến đổi theo quy tắc trên để \(k\) bằng \(1\). Trong trường hợp không thể biến đổi \(k\) bằng \(1\) thì in ra kết quả \(-1\).

Input

• Một dòng chứa số nguyên \(k\) \((k \leq 10^{9})\).

Output

• Số nguyên \(m\) là số lần biến đổi để \(k\) bằng \(1\).

Example

12 

3

10

-1

Một số tự nhiên được gọi là số Py−ta−go là số được tạo thành từ việc ghép \(3\) số tự nhiên \(a, b, c\) theo một trật tự bất kì với nhau (không thay đổi trật tự các chữ số trong mỗi số \(a, b, c\)), trong đó \(3\) số \(a, b, c\) thỏa mãn điều kiện tổng bình phương của \(2\) số nào đó trong \(3\) số này bằng bình phương của số còn lại.

Ví dụ: Với \(3\) số \(a = 6, b = 8, c = 10\), ta có \(6^{2} + 8^{2} = 10^{2}\) và nếu ghép chúng lại với nhau theo một trật tự bất kì thì ta có được tất cả \(6\) số Py−ta−go như sau: \(6810, 6108, 8610, 8106, 1068, 1086\).

Yêu cầu: Cho \(x\) là một số Py−ta−go được ghép từ bộ ba số \(a, b, c\) như đã trình bày ở trên. Hãy tìm số lớn nhất trong \(3\) số \(a, b, c\).

Input

• Một dòng chứa số nguyên dương \(x\) có ít nhất \(3\) chữ số và có nhiều nhất \(24\) chữ số.

Output

• Ghi ra số nguyên dương cần tìm theo yêu cầu của đề. Nếu có nhiều kết quả thì chỉ ghi ra số lớn nhất trong các kết quả tìm được.

Example

6810 

10

Cho một xâu \(S\) chỉ gồm các kí tự thường trong bảng chữ cái tiếng Anh. Hãy tìm ra tất cả các từ vựng có trong xâu \(S\). Một từ vựng có được bằng cách ghép một số kí tự liên tiếp lấy từ xâu \(S\), giữ nguyên thứ tự của chúng, thỏa mãn một trong hai điều kiện sau:

• Bắt đầu bằng một nguyên âm (là các chữ cái: a, e, i, o, u) và kết thúc bằng một phụ âm (là các chữ cái còn lại).
• Bắt đầu bằng một phụ âm và kết thúc bằng một nguyên âm.

Yêu cầu: Tìm số lượng từ vựng có trong xâu \(S\) theo quy tắc trên.

Input

• Một dòng chứa xâu \(S\) \((|S| \leq 10^{6})\).

Output

• Ghi ra một số nguyên là kết quả tìm được.

Scorning

• Subtask \(1\) (\(40\%\) số điểm): \(|S| \leq 10^{4}\).
• Subtask \(2\) (\(60\%\) số điểm): không có rằng buộc gì thêm.

Example

adceba

9