Năm may mắn

Trong quan niệm của Bảo, một năm gọi là may mắn nếu nó chỉ có một chữ số khác 0.

Ví dụ: 1, 10, ... là năm may mắn. Biết năm nay là năm n, hỏi Bảo phải đợi bao năm nữa để đến năm may mắn.

Input

Output

Example

Test 1

Test 2

Số Chính Phương

Định nghĩa: số chính phương là bình phương của một số tự nhiên. Ví dụ: 9 là số chính phương vì 9 = 3 x 3.

Yêu cầu: Cho số tự nhiên n. Đếm số lượng số m có giá trị từ 1 đến n sao cho:

• m là số chính phương
• m chia hết cho 8 hoặc m chia hết cho 6

Input

Output

Example

Test 1

Note

Các số thỏa mãn là: 16 = 4^2, 36 = 6^2, 64 = 8^2.

8 và 6

Khang rất thích hai chữ số 8 và 6.

Nhân dịp kỳ thi Tin học trẻ đang tới gần, Khang dành riêng cho các bạn học sinh một bài tập như sau:

Với số khởi đầu là 86, với mỗi lần biến đổi theo qui tắc sau:

• Lấy số nhân cho 8 rồi cộng cho 6
• Sau đó lấy số mod cho m (2 ≤ m ≤ 100000)

Input

Output

Example

Test 1

Note

Với m = 88866, sau 3 lần biến đổi:

• Lần 1: S1 = (86 x 8 + 6) mod 88866 = 694
• Lần 2: S2 = (694 x 8 + 6) mod 88866 = 5558
• Lần 3: S3 = (5558 x 8 + 6) mod 88866 = 44470

Test 2