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?

Dữ liệu:
Một dòng duy nhất, chứa số \(x\) - Vị trí nhà bạn.

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

Sample Input

5

1

Sample Input

12

3

Cho dãy số \(1;4;7;10;13;16;19; ...\). 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.

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.

Sample Input

5

Sample Output

15

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.

Ví dụ: \(a=5; b= 49\) thì kết quả là \(9; 16; 25; 36; 49\)

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 100.000.000 =10^{8}\))

Output

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

Sample Input

5
49

Sample Output

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.

Sample Input

1
2 
3 
10

Sample Output

15

Giải thích Những số chia hết cho \(2\) hoặc cho \(3\) là $2, 3, 4, 6, 8, 9, 10, 12, 14, 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, …\)

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)

Dữ liệu

• 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)\)

Kết quả

• 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

Sample Input

10
1
2
3
4
5
6
7
8
9
1000

Sample Output

1
2
4
5
7
8
10
11
14
1666

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