Ôn luyện vào chuyên Tin #06

Thời điểm bất kỳ được coi là đối xứng nếu như số giờ và số phút ở thời điểm đó đối xứng nhau.

Ví dụ: Những thời điểm đối xứng "\(00:00\)" , "\(12:21\)". Những thời điểm không đối xứng "\(00:01\)" , "\(11:21\)" \(!\)

Yêu cầu: Cho một thời điểm bất kỳ "\(HH:MM\)" với \(HH\) là số giờ (00->23), \(MM\) là số phút (00->59). Tìm thời điểm đối xứng sớm nhất sau thời điểm đã cho.

Input

• \(1\) chuỗi ký tự có dạng "\(HH:MM\)" với \(HH\) là số giờ (00->23), \(MM\) là số phút (00->59).

Output

• Thời điểm đối xứng sớm nhất sau thời điểm đã cho, biểu diễn dưới dạng "\(HH:MM\)" với \(HH\) là số giờ (00->23), \(MM\) là số phút (00->59).

Example

12:21 

13:31

23:59 

00:00

Một số tự nhiên được cho là số may mắn nếu các chữ số của số đó chỉ có thể là số \(6\) hoặc số \(9\).

Yêu cầu: Cho số \(n \ (1 \leq n \leq 55)\), hãy tìm số lượng số may mắn có số chữ số \(\leq n\).

Input

• 1 số nguyên dương \(n \ (1 \leq n \leq 55)\).

Output

• Số lượng số may mắn có số chữ số không quá \(n\).

Example

2 

6

Bội chung nhỏ nhất của \(2\) số là số nguyên dương nhỏ nhất mà chia hết cho cả hai số đó.

Ký hiệu \(LCM(a,b)\) là bội chung nhỏ nhất của hai số \(a\) và \(b\). \(LCM(a,b,c)\) là bội chung nhỏ nhất của \(a\), \(b\) và \(c\).

Yêu cầu: Cho số \(n(1 \leq n \leq 10^6)\), hãy tìm giá trị lớn nhất bội chung nhỏ nhất của ba số nguyên dương bất kỳ không lớn hơn \(n\).

Input

• \(1\) số nguyên dương \(n \ (1 \leq n \leq 10^6)\).

Output

• \(MAX( LCM(i,j,k) )\) trong đó \((1 \leq i,j,k \leq n)\).

Example

9 

504