Cho một số tự nhiên N. Hỏi N có thể tách thành tổng của hai số tự nhiên lẻ khác nhau được không?

Dữ liệu vào từ thiết bị vào chuẩn

Gồm một dòng chứa một số tự nhiên N (N≤100).

Kết quả ghi ra thiết bị ra chuẩn

Nếu có thể tách được N theo yêu cầu đề bài thì in ra 1, nếu không tách được thì in ra 0.

Ví dụ

Cho một vòng số gồm 10 chữ số từ ~0~ đến ~9~ như hình đồng hồ.

Phép dịch chữ số là biến chữ số đó thành chữ số kế tiếp theo chiều kim đồng hồ.
Ví dụ:

• Dịch chữ số ~1~ một lần → ~2~
• Dịch chữ số ~9~ một lần → ~0~

Yêu cầu:
Cho số tự nhiên ~N~, hỏi sau khi dịch từng chữ số của ~N~ đi ~K~ lần, ta thu được số mới là bao nhiêu?

Input

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

Output

• Một dòng là kết quả sau khi dịch toàn bộ các chữ số của ~N~ đi ~K~ lần.

Subtasks

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

Sample Test

Input

5
1

Output

6

Input

83
2

Output

05

Note

• Với ~83~:
  
  • Dịch chữ ~8~ đi 2 lần → ~0~
  • Dịch chữ ~3~ đi 2 lần → ~5~
    → Kết quả: ~05~ (giữ đúng định dạng hai chữ số)

Cho dãy số ~A~ có quy luật như sau:
~1, 3, 2, 6, 4, 12, 8, 24, 16, 48, 32, 96, 64, 192, 128, \dots~
(Số ở vị trí thứ ~i~ bằng hai lần số ở vị trí thứ ~i - 2~)

Lấy hai chữ số cuối cùng của các số trong dãy ~A~ ta được dãy số ~B~:
~1, 3, 2, 6, 4, 12, 8, 24, 16, 48, 32, 96, 64, 92, 28, \dots~

Yêu cầu:
Cho số tự nhiên ~N~. Tính tổng ~N~ số đầu tiên của dãy số ~B~.

Input

• Gồm một dòng chứa một số tự nhiên ~N~
  > ~(N \leq 10^{12})~

Output

• Gồm một dòng, chứa một số tự nhiên là kết quả của bài toán.

Subtasks

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

Sample Test

Input

4

Output

12

Note

• Bốn phần tử đầu của dãy ~B~ là: ~1, 3, 2, 6~
• Tổng là: ~1 + 3 + 2 + 6 = 12~

Cho số tự nhiên ~N~. Hãy tìm số tự nhiên ~K~ nhỏ nhất sao cho tổng các số lẻ từ ~1~ đến ~K~ lớn hơn tổng các số chẵn từ ~K + 1~ đến ~N~.

Input

• Gồm một dòng chứa một số tự nhiên ~N~ ~(N \le 10^9)~

Output

• Gồm một dòng chứa một số tự nhiên là số ~K~ nhỏ nhất thoả mãn.

Subtask

• Subtask ~1~ (~80\%~ số điểm): ~n \le 1000~.
• Subtask ~2~ (~20\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

10

Sample Output 1

8

Explanation 1

~1 + 3 + 5 + 7 > 10~

Số chẵn tròn là số chẵn mà viết ngược lại vẫn là số chẵn.
Ví dụ: các số ~234, 4, 6708, \dots~ là số chẵn tròn;
còn các số ~14, 23, 1246, \dots~ không phải là số chẵn tròn.

Yêu cầu:
Cho một số tự nhiên ~N~. Đếm xem có bao nhiêu số chẵn tròn nhỏ hơn ~N~.

Input

• Gồm một dòng chứa một số tự nhiên ~N~
  > ~(N \leq 10^9)~

Output

• Gồm một dòng chứa một số tự nhiên là kết quả của bài toán.

Subtasks

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

Sample Test

Input

24

Output

6

Note

• Các số chẵn tròn nhỏ hơn ~24~ là: ~2, 4, 6, 8, 20, 22~

Cho một số tự nhiên ~S~ có ~N~ chữ số và một số tự nhiên ~K~.

Yêu cầu:
Hãy thay đổi tối đa ~K~ chữ số của ~S~ để tạo ra một số mới nhỏ nhất có ~N~ chữ số và chia hết cho 2.

Input

• Dòng đầu tiên chứa một số tự nhiên ~N~ — là số lượng chữ số của ~S~
• Dòng thứ hai chứa một số tự nhiên ~S~ có đúng ~N~ chữ số
• Dòng thứ ba chứa một số tự nhiên ~K~
  > ~(2 \leq N \leq 1000;~ ~1 \leq K \leq N)~

Output

• Ghi ra một số tự nhiên là số mới thoả mãn yêu cầu đề bài.

Subtasks

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

Sample Test

Input

4
4913
1

Output

4910

Note

• Chỉ được thay đổi 1 chữ số
• Thay chữ số cuối từ 3 thành 0 → số nhỏ nhất thoả mãn điều kiện là ~4910~ (chia hết cho 2)