Bố đang dạy Luffy học xem giờ. Nhà Luffy có chiếc đồng hồ treo tường, hiện tại đang chỉ \(2\) giờ. Bố đố Luffy biết sau ít nhất bao nhiêu giờ thì đồng hồ chỉ \(K\) giờ?

Input

• Một số tự nhiên \(K\) \((1 \leq K \leq 12)\).

Output

• Một số tự nhiên là kết quả của câu đố mà bố đố Luffy.

Example

5

3

1

11

Luffy có \(A\) viên bi, mỗi ngày bố cho Luffy thêm \(2\) viên bi. Hỏi sau bao nhiêu ngày thì Luffy có nhiều hơn \(B\) viên bi?

Input

• Dòng đầu tiên chứa một số tự nhiên \(A\) \((1 \leq A \leq 10^{9})\).
• Dòng thứ hai chứa một số tự nhiên \(B\) \((1 \leq B \leq 10^{9})\).

Output

• Một số tự nhiên là kết quả của bài toán.

Example

3
5

2

5
3

0

Zoro viết liên tiếp các tháng từ tháng \(1\) đến tháng \(12\), rồi cứ tiếp tục như thế tạo thành một số “dãy tháng” dài vô tận: 123456789101112123456789101112123456...

Hãy tính tổng của \(K\) chữ số đầu tiên trong số “dãy tháng” của Zoro.

Input

• Một số tự nhiên \(K\) (\(1 \leq K \leq 10^9\)).

Output

• Một số tự nhiên là kết quả của bài toán.

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(K \leq 1000\).
• Subtask \(2\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

3

6

Sanji định nghĩa một số đẹp bậc năm là số có từ hai chữ số trở lên và chỉ gồm đúng \(1\) chữ số khác chữ số \(5\). Ví dụ về các số đẹp bậc năm: \(15, 25, 35, 45,50, 51, 52, 53, 54, 56, 57, 58, 59, 65, 75, 85, 95, 155, 255, \ldots\) Viết các số tạo thành dãy số đẹp bậc năm tăng dần. Hãy tìm số nhỏ thứ \(K\) của dãy số đó.

Input

• Một số tự nhiên \(K\) (\(1 \leq K \leq 1000\)).

Output

• Gồm một dòng là kết quả của bài toán.

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(K \leq 150\).
• Subtask \(2\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

5

50

11

57

Các thí sinh của bảng A là nhỏ tuổi nhất trong kì thi Tin học trẻ. Để các thí sinh có tâm lý tốt trước khi bắt đầu cuộc thi, Ban tổ chức đã chuẩn bị \(M\) cái kẹo để chia cho \(N\) thí sinh. Tuy nhiên, Ban tổ muốn các thí sinh phải có số kẹo bằng nhau. Vậy Ban tổ chức cần chuẩn bị thêm bao nhiêu cái kẹo nữa để có thể chia đều cho \(N\) thí sinh.

Input

• Dòng đầu tiên chứa số tự nhiên \(M \leq 10^9\)
• Dòng thứ hai chứa số tự nhiên \(N \leq 10 ^9\)

Output

• Ghi ra một số duy nhất là số lượng kẹo mà Ban tổ chức cần chuẩn bị thêm.

Example

12
5 

3

Tại kì thi Tin học trẻ Ban tổ chức sử dụng các số tự nhiên may mắn để đánh số báo danh như một lời chúc các thí sinh làm bài tốt. Ban tổ chức quan niệm số không may mắn là số chia hết cho \(5\) hoặc số chia cho \(5\) dư \(3\), các số khác là số may mắn. Ví dụ các số may mắn: \(1, 2, 4, 6, 7, 9, 11, 12, 14,…\)
Biết Ban tổ chức sử dụng tất cả các số may mắn nhỏ hơn \(N\) để đánh số báo danh, hãy tính tổng các giá trị may mắn được sử dụng.

Input

• Dòng đầu tiên chứa một số tự nhiên \(N\).

Output

• Ghi ra một số duy nhất là tổng các giá trị may mắn nhỏ hơn \(N\).

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(1 \leq N \leq 10^4\).
• Subtask \(2\) (\(100\%\) số điểm): \(1 \leq N \leq 10^8\).

Example

15 

66

Sau khi tham gia cuộc thi, các thí sinh sẽ ra ngoài để chơi các trò chơi trong lúc đợi kết quả chấm bài vẽ hình. Trong đó, trò chơi chữ số cuối cùng là trò chơi được yêu thích nhất. Các thí sinh tham gia trò chơi sẽ thay số \(X\) nhận được bởi tổng các chữ số của \(X\), cứ như vậy cho đến khi \(X\) chỉ còn 1 chữ số. Ví dụ \(X = 148\) thì sẽ thay \(X = 1+ 4 + 8 = 13\), sau đó lại thay \(X = 13\) thành \(X = 1 + 3 = 4\) thì kết thúc. Có rất nhiều thí sinh thích trò chơi này vì không ai dự đoán trước được số cuối cùng mà mình nhận được. Để chọn được thí sinh xuất sắc nhất thì ban tổ chức có thêm một yêu cầu là hãy tính tổng các số chữ số cuối cùng của các số từ \(A\) đến \(B\) nhanh nhất có thể. Ai cũng muốn chiến thắng để có thêm giải thưởng phụ là thí sinh nhanh nhẹn nhất. Em hãy lập trình để giải bài toán trên.

Input

• Dòng đầu tiên chứa số tự nhiên \(A\)
• Dòng thứ hai chứa số tự nhiên \(B\)

Output

• Kết quả: Ghi ra một số là tổng các chữ số cuối cùng của các số từ \(A\) đến \(B\)

Scoring

• Subtask \(1\) (\(60\%\) số điểm): $1 \leq A, B \leq 10^4 $.
• Subtask \(2\) (\(100\%\) số điểm): $1 \leq A, B \leq 10^9 $.

Example

395
398 

20

Người ta mắc bóng đèn màu xung quanh một bảng quảng cáo hình vuông có chiều dài \(a\) \((dm)\), hai bóng đèn liên tiếp cách nhau \(5\) \((cm)\). Em hãy viết chương trình để đưa ra màn hình số lượng bóng đèn cần mắc.

Ví dụ: \(a = 1\), thì số bóng đèn cần mắc là \(8\).

Input

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

Output

• Một số nguyên duy nhất là số lượng bóng đèn cần mắc.

Example

3

24

Cho trước \(4\) số nguyên \(a, b, c, d\). Chúng ta sẽ chọn các số nguyên \(x\) và \(y\) sao cho \(a\le x\le b\) và \(c\le y\le d\).

Yêu cầu: Tìm giá trị nhỏ nhất có thể có của \(x − y\).

Input

• Dòng thứ nhất chưa \(2\) số nguyên \(a,b\ (0< a,b \le 10^{12})\).
• Dòng thứ hai chưa \(2\) số nguyên \(c,d\ (0< c,d \le 10^{12})\).

Output

• In ra giá \(x-y\) nhỏ nhất.

Example

0
10
0
10

-10

10
15
7
9

1

Polycarp không thích các số nguyên chia hết cho \(3\) hay có tận cùng bằng \(3\) (trong biểu diễn thập phân của số). Các số thỏa mãn cả hai điều kiện, Polycarp cũng không thích.

Polycarp bắt đầu viết các số nguyên dương (lớn hơn \(0\)) mà anh ấy thích: \(1, 2, 4, 5, 7, 8, 10, 11, 14, 16, …\).

Yêu cầu: Hãy in ra số thứ \(k\) trong dãy này (các số được đánh thứ tự từ \(1\)).

Input

• Một dòng chứa một số nguyên dương \(k\ (1 \le k \le 10^9)\).

Output

• In ra một dòng chứa số nguyên dương \(x\) - là số thứ \(k\) trong dãy mà Polycarp viết ra.

Example

3

4

Số cân bằng là số:

• Có số lượng các chữ số là số chẵn.
• Nữa nhóm ký tự bên trái giống nữa nhóm bên phải.

Ví dụ: \(66, 1212; 348348\) là số cân bằng, \(666, 1221; 334488\) không phải là số cân bằng.

Yêu cầu Cho giá trị \(n\), hãy tìm các số cân bằng không vượt quá \(n\).

Input

• Một dòng chứa một số nguyên \(n\ (0< n \le 10^{12})\).

Output

• In ra số lượng số cân bằng không vượt quá \(n\).

Example

33

3

1333

13

NMột mảng tường vuông có kích thước \(n×n\) hình vuông đơn vị (với \(n\) là số chẵn) được trang trí hoa văn sau:

Yêu cầu: Nhập vào số tự nhiên chẵn \(n\ (2≤n≤10)\), hãy vẽ mảng tường \(n×n\) tương ứng.

Chú ý:

• Tô màu có dạng giống hình vẽ, có thể thay màu khác.
• Không sử dụng nhân vật giống hình vẽ.

Chấm điểm: Vẽ được hình vuông đúng mà không tô màu thì trừ 40% số điểm của mỗi trường hợp tương ứng.

Bạn được đưa cho một tấm bảng hình chữ nhật gồm \(M×N\) ô vuông. Ngoài ra, bạn được cung cấp một số lượng không giới hạn quân cờ domino tiêu chuẩn có kích thước \(2 × 1\) (các quân cờ được phép xoay 90 độ). Bạn được yêu cầu đặt càng nhiều quân cờ domino càng tốt trên bảng sao cho đáp ứng các điều kiện sau:

• Mỗi quân domino bao hoàn toàn 2 hình vuông trên bảng.
• Không có 2 quân domino nào đè lên nhau hay mỗi ô trên bảng được lấp bởi tối đa 1 quân domino.
• Mỗi quân domino nằm hoàn toàn bên trong bàn cờ. Nó được phép chạm vào các cạnh của bảng.

Yêu cầu: Tìm số quân cờ domino tối đa có thể đặt được thỏa mãn các điều kiện trên.

Dữ liệu:

• Dòng đầu tiên chứa số tự nhiên \(M\ (1≤M≤1 000)\).
• Dòng thứ hai chứa số tự nhiên \(N\ (1≤N≤1 000)\).

Kết quả: In ra một số tự nhiên duy nhất là số quân cờ domino tối đa có thể đặt được.

Scoring

• Subtask \(1\) (\(60\) điểm): \(M * N \leq 40\).
• Subtask \(2\) (\(40\) điểm): Không có ràng buộc gì thêm.

Example

2 
4

4

3 
3

4

Xâu giống nhau là xâu chỉ chứa một loại ký tự bất kỳ.

Bạn có được “phép thuật” lấy hai ký tự \(A,B\) bất kỳ để biến thành một ký tự \(C\).

Ví dụ: Xâu \(ABC\) có thể biến đổi thành xâu \(CC\)

Yêu cầu: Cho xâu \(S\) chỉ gồm ba ký tự \(A,B,C\), bạn có thể biến đổi thành xâu giống nhau hay không?

Dữ liệu: Một xâu ký tự \(S\) chỉ gồm ba ký tự \(A,B,C\) có độ dài không qua 1 000 ký tự.

Kết quả: In ra chữ YES nếu biến đổi xây \(S\) thành xâu giống nhau, ngược lại in chữ NO

Example

CCCB

NO

AAABBCB

YES

Note

• Ở test 2 đáp án là CCCC

Nam là nhà khảo cổ học, anh đã thăm dò và phát hiện nhiều cổ vật rất có giá trị. Để dễ quản lí các cổ vật, anh ta đánh số thứ tự cho các cổ vật, có \(n\) cổ vật được đánh số \(1, 2, 3, ... n\). Nam muốn biết với n cổ vật thì tổng các chữ số dùng để đánh số thứ tự là bao nhiêu?

Ví dụ: Có \(n=12\) cổ vật thì tổng các chữ số để đánh số thứ tự là : \(1+2+3+4+5+6+7+8+9+1+0+1+1+1+2=51\)

Yêu cầu Cho giá trị \(n\), hãy tính tổng các chữ số dùng cho việc đánh số thứ tự \(n\) cổ vật

Dữ liệu: Một số tự nhiên \(n\ (n≤10^{12})\).

Kết quả: Một số tự nhiên duy nhất là tổng các chữ số dùng để đánh số thứ tự của \(n\) cổ vật.

Scoring

• Có 60% số điểm của bài toán với \(n≤1 000 000\).
• Có 40% số điểm của bài toán với \(1 0000 000≤n≤10^{12}\).

Example

12

51

8

36

Hai bạn Trí và Tuệ đang rèn luyện để tham gia vào ngày hội tháng 3. Trong ngày hội này có một mục hai ban rất thích đó mục tạo và giải mật thư.

Quá trình tạo mật thư là quá trình biến đổi đoạn văn bản gốc có ý nghĩa theo quy tắc nhất định thành đoạn văn bản khi nhìn vào khó mà đoán được văn bản gốc.

Bạn Trí đã nghĩ ra một cách như sau: Sau mỗi kí tự ở vị trí thứ \(K\) của văn bản gốc ta thêm vào \(K\) chữ cái hoặc số bất kì. Trong bản gốc và mật thư không chứa dấu cách. Cuối cùng đem đảo ngược toàn bộ văn bản vừa tạo ra.

Ví dụ: Văn bản gốc là: TinHoc thì mật thư do bạn Trí tạo ra có dạng như sau:

• Bước 1: Tạo thành văn bản sau: Tliomn43kHhk4jokhio9cjhdf8d.
• Bước 2: Đem đoạn văn bản trên viết ngược lại thành mật thư sau: d8fdhje9oihkoj4khHk34nmoi1T

Yêu cầu: Bạn Trí đã gửi mật thư trên đến cho bạn Tuệ. Em hãy giúp bạn Tuệ lập trình để giải mã các bức mật thư mà bạn Trí đã gửi đến theo qui tắc trên.

Dữ liệu: Một xâu ký tự \(S\) là mật thư có độ dài không qua 1 000 ký tự.

Kết quả: In ra xâu văn bản gốc

Example

d8fdhjc9oihkoj4khHk34nmoilT

TinHoc

6tuyjghu678uj8ahd987hkkjhC4reihga2H

HaiChau

Bạn Trí được phân công sẽ mua quà để làm phần thưởng khi kết thúc ngày hội tháng 3. Khi đến cửa hàng thì bạn được cho biết là cửa hàng có các loại quà 2 nghìn đồng, 5 nghìn đồng và 10 nghìn đồng.

Để đảm bảo với số lượng phần thưởng ban tổ chức có quy định là bạn Trí phải mua loại 2 nghìn gấp đôi loại 5 nghìn và loại 5 nghìn phải nhiều hơn loại 10 nghìn 5 phần quà và loại 10 nghìn phải có ít nhất 1 món quà.

Với 1 số tiền được ban tổ chức giao cho, Trí đang phân vân không biết mình có những cách mua quà như thế nào. Em hãy lập trình để đếm xem bạn Trí có bao nhiêu cách để có thể mua những món quà trên. Không nhất thiết phải sử dụng hết số tiền ban tổ chức đã giao.

Dữ liệu: Nhập vào số tiền là 1 số tự nhiên N. (\(10.000 \le N \le 20.000.000\))

Kết quả: Số cách có thể mua quà

Example

100000

2

20000

0

Ban tổ chức ngày hội tháng 3 đã đưa ra một hộp quà bí mật. Trên hộp quà có xuất hiện 1 số tự nhiên \(N\) và một dãy số tự nhiên: \(2;3;7;8; 12 ; 13 ; 17 ; ...\). Mật mã để mở được hộp quà chính là số hạng thứ \(N\) của dãy số trên. Trí và Tuệ đang suy nghĩ cách giải để tìm ra được mật mã. Hãy lập trình đề giúp 2 bạn tìm ra mật mã của hộp quà với \(N\) được nhập vào.

Dữ liệu: Nhập vào số 1 số tự nhiên \(N\) (\(1 \le N \le 1000.000.000.000\))

Kết quả: Số hạng thứ \(N\) của dãy đã cho

Example

5

12

10

23