Ôn luyện thi Khu vực #10

Một chú voi đi thăm bạn. Nhà của chú nằm ở vị trí \(0\) (đầu đường), và nhà bạn thì ở vị trí thứ \(x\) trên con đường. Mỗi bước chú có thể đi qua \(1, 2, 3, 4\) hoặc \(5\) ngôi nhà.

Hỏi, cần đi ít nhất bao nhiêu bước để chú voi có thể tới nhà thăm bạn?

Input

• Một dòng duy nhất, chứa số \(x\) - vị trí nhà bạn.

Output

• In ra số bước ít nhất chú voi cần đi để từ điểm \(0\) đến điểm \(x\).

Example

5

1

12

3

Cho dãy số \(1; 4; 7; 10; 13; 16; 19; \dots\). Cho số \(n\), hãy tính tổng chữ số cuối cùng của \(n\) số đầu tiên trong dãy số đã cho.

Ví dụ: \(n = 5\) thì kết quả là \(15\), vì chữ số tận cùng của 5 số đầu tiên là \(1 + 4 + 7 + 0 + 3 = 15\).

Yêu cầu: Cho biết số \(n\), hãy tính tổng theo yêu cầu.

Input

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

Output

• Một dòng chứa số nguyên dương là kết quả của bài toán.

Example

5

15

Scoring

• Nếu chương trình chạy đúng những trường hợp \(N \le 10^6\), thí sinh sẽ được \(60\) điểm.
• Nếu chương trình chạy đúng những trường hợp \(N \le 10^9\), thí sinh sẽ được \(100\) điểm.

Số chính phương là số bằng bình phương đúng của một số nguyên. Ví dụ \(9=3^2; 36=6^2\) là các số chính phương.

Yêu cầu

Tìm các số chính phương trong đoạn từ \(a\) đến \(b\), với \(a, b\) (\(a \le b\)) được nhập từ bàn phím.

Input

• Dòng đầu tiên chứa số nguyên dương \(a\).
• Dòng thứ hai chứa số nguyên dương \(b\) (\(a \le b \le 10^8\)).

Output

• Một dòng chứa các số chính phương trong đoạn từ \(a\) đến \(b\).

Example

5
49

9 16 25 36 49

Bạn được cho 2 số nguyên dương \(a\) và \(b\).

Viết chương trình tìm số thứ \(n\) chia hết cho \(a\) hoặc \(b\).

Input

• Dòng đầu tiên chứa số nguyên dương \(T\) (\(T \leq 100\)) - là số câu hỏi.
• \(T\) nhóm dòng tiếp theo, mỗi nhóm chứa 3 dòng chứa 3 số nguyên dương \(a, b, n\) (\(a, b \leq 10^4, n \leq 10^9\)).

Output

• Gồm \(T\) dòng, mỗi dòng chứa câu trả lời cho mỗi câu hỏi.

Example

1
2
3
10

15

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, \dots\)

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

• Dòng đầu tiên chứa một số nguyên dương \(t\ (1 \le t \le 100)\) - số lượng bộ trường hợp cần giải quyết.
• Sau đó là \(t\) dòng, mỗi dòng chứa một số nguyên dương \(k\ (1 \le k \le 10^9)\).

Output

• Với mỗi trường hợp, 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

10
1
2
3
4
5
6
7
8
9
1000

1
2
4
5
7
8
10
11
14
1666

(Nguồn: CF 1560A có mở rộng thêm giới hạn)