Yêu cầu

Trong một chiếc hộp có: ~A~ quả bóng đỏ, ~B~ quả bóng xanh và ~C~ quả bóng vàng. Các quả bóng cùng màu thì giống hệt nhau. Bạn lấy bóng ngẫu nhiên ra khỏi hộp mà không nhìn vào bên trong. Hãy tính số quả bóng ít nhất cần lấy ra để chắc chắn rằng trong số bóng đã lấy có đủ cả ~3~ màu: đỏ, xanh và vàng.

Input

Gồm ba dòng, mỗi dòng ghi một số tự nhiên, lần lượt là giá trị của ~A~, ~B~ và ~C~ (~1~ ~\le~ ~A, B, C~ ~\le~ ~100~).

Output

Ghi ra một dòng chứa một số tự nhiên duy nhất là số quả bóng ít nhất cần lấy ra.

Input

3
5
2

Output

9

• Giải thích: Trong trường hợp xui xẻo nhất (trường hợp xấu nhất), ta có thể lấy hết toàn bộ số bóng của hai màu có số lượng nhiều nhất trước mà vẫn chưa có đủ 3 màu. Ở đây, hai màu có nhiều bóng nhất là xanh (5 quả) và đỏ (3 quả), tổng cộng là 8 quả. Vì vậy, ta phải lấy thêm 1 quả nữa (chắc chắn sẽ là màu vàng) thì mới đảm bảo có đủ cả 3 màu. Kết quả là 8 + 1 = 9.

Input

1
1
1

Output

3

• Giải thích: Mỗi màu chỉ có đúng 1 quả bóng. Do đó, chỉ khi lấy đủ cả 3 quả thì ta mới chắc chắn có đủ 3 màu.

Yêu cầu

Pink rất thích nhìn đồng hồ điện tử hiển thị theo dạng ~HH:MM~, trong đó giờ từ ~00~ đến ~23~ và phút từ ~00~ đến ~59~.

Pink gọi một thời điểm là "đồng điệu" nếu tổng các chữ số của phần giờ bằng đúng tổng các chữ số của phần phút. Ví dụ: ~14:32~ là thời điểm đồng điệu vì ~1 + 4 = 3 + 2 = 5~; ~07:07~ cũng là thời điểm đồng điệu vì ~0 + 7 = 0 + 7~.

Hiện tại đồng hồ đang chỉ ~H~ giờ ~M~ phút. Hãy tính xem, tính cả thời điểm hiện tại, trong vòng ~K~ phút tiếp theo có bao nhiêu thời điểm đồng hồ hiển thị thời gian đồng điệu. (Lưu ý: khoảng thời gian này có thể kéo dài sang ngày hôm sau hoặc nhiều ngày sau đó).

Input

Gồm ba dòng, mỗi dòng ghi một số tự nhiên, lần lượt là giá trị của ~H~, ~M~ và ~K~ (~0~ ~\le~ ~H~ ~\le~ ~23~; ~0~ ~\le~ ~M~ ~\le~ ~59~; ~0~ ~\le~ ~K~ ~\le~ ~2880~).

Output

Ghi ra một dòng chứa một số tự nhiên duy nhất là số thời điểm đồng điệu tìm được.

Ví dụ

Input

23
58
5

Output

1

• Giải thích: Ta xét ~6~ thời điểm, từ phút hiện tại đến 5 phút sau lần lượt là: ~23:58, 23:59, 00:00, 00:01, 00:02, 00:03~. Trong số này, chỉ có ~00:00~ là thời điểm đồng điệu (vì ~0 + 0 = 0 + 0~), do đó kết quả là 1.

Input

7
7
0

Output

1

• Giải thích: Vì ~K~ = 0 nên ta chỉ xét đúng thời điểm hiện tại là ~07:07~. Đây là thời điểm đồng điệu nên kết quả là 1.

Ràng buộc

• Có ~50%~ số test tương ứng với ~50%~ số điểm của bài thỏa mãn: ~K~ ~\le~ ~60~;
• ~50%~ số test còn lại tương ứng với ~50%~ số điểm của bài thỏa mãn: Không có ràng buộc nào thêm.

Yêu cầu

Cho một bàn cờ vua kích thước ~N~ ~\times~ ~N~. Các hàng được đánh số từ ~1~ đến ~N~ từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~N~ từ trái sang phải.

Một quân hậu đang đứng ở ô (~x, y~). Quân hậu được đi theo luật cờ vua, nghĩa là trong một nước đi, quân hậu có thể di chuyển đến bất kỳ ô nào cùng hàng, cùng cột hoặc cùng đường chéo với ô hiện tại, miễn là ô đó vẫn nằm trong bàn cờ.

Hãy đếm xem có bao nhiêu ô (~u, v~) mà quân hậu có thể đi tới trong đúng ~1~ nước đi và thỏa mãn điều kiện tổng ~u + v~ là số chẵn.

Input

Gồm ba dòng, mỗi dòng ghi một số tự nhiên, lần lượt là giá trị của ~N, x~ và ~y~ (~1~ ~\le~ ~x, y~ ~\le~ ~N~ ~\le~ ~10^8~).

Output

Ghi ra một dòng chứa một số tự nhiên duy nhất là số cách chọn ô tiếp theo thỏa mãn yêu cầu.

Ví dụ

Input

8
4
4

Output

19

• Giải thích: Quân hậy đang ở ô ~(4,4)~ trên bàn cờ ~8 x 8~. Đếm tất cả các ô mà quân hậy đi tới được trong một nước đi và có tổng số hàng cộng số cột là số chẵn, ta được ~19~ ô. Trong hình bên dưới ô quân hậy đang đứng được tô màu đỏ, các ô đi tới được trong một bước thỏa mãn điều kiện được tô màu xanh.

Input

5
2
1

Output

5

• Giải thích: Quân hậy đang ở ô ~(2,1)~ trên bàn cờ ~5 x 5~. Có đúng ~5~ ô mà quân hậu đi tới được trong một nước đi mà thỏa mãn điều kiện ~u + v~ là số chẵn.

Ràng buộc

• Có ~40%~ số test tương ứng với ~40%~ số điểm của bài thỏa mãn: ~N~ ~=~ ~8~;
• ~40%~ số test khác tương ứng với ~40%~ số điểm của bài thỏa mãn: ~N~ ~\le~ ~200~;
• ~20%~ số test còn lại tương ứng với ~20%~ số điểm của bài thỏa mãn: ~N~ ~\le~ ~10^8~.

Yêu cầu

Cho số tự nhiên ~N~. Ta lập một bảng vuông kích thước ~N~ ~\times~ ~N~, gồm các số tự nhiên từ ~1~ đến ~N^2~. Các số được điền vào bảng theo quy luật như hình sau:

Cho hai số tự nhiên ~X~ và ~Y~. Hãy tính tổng các số nằm trên dòng ~X~ và các số nằm trên cột ~Y~ của bảng. Lưu ý: nếu một số nằm ở giao điểm của dòng ~X~ và cột ~Y~ thì chỉ được cộng ~1~ lần.

Input

Gồm ba dòng, mỗi dòng ghi một số tự nhiên, lần lượt là giá trị của ~N, X~ và ~Y~ (~1~ ~\le~ ~X, Y~ ~\le~ ~N~ ~\le~ ~10^8~).

Output

Ghi ra một dòng chứa một số tự nhiên duy nhất là kết quả của tổng cần tìm sau khi chia lấy phần dư cho ~2026~.

Ví dụ

Input

4
2
3

Output

67

• Giải thích:
  • Với ~N~ = 4, bảng được điền như sau: 1 2 3 4 9 10 11 12 13 14 15 16 5 6 7 8
  • Dòng ~2~ có tổng là ~9 + 10 + 11 + 12 = 42~. Cột ~3~ có tổng là ~3 + 11 + 15 + 7 = 36~. Ô giao nhau tại dòng ~2~, cột ~3~ có giá trị là 11. Tổng cần tìm là: ~42 + 36 - 11 = 67~. Do ~67~ nhỏ hơn ~2026~ nên kết quả chia dư vẫn là ~67~.

Input

3
3
1

Output

23

• Giải thích:
  • Với ~N~ = 3, bảng được điền như sau: 1 2 3 7 8 9 4 5 6
  • Dòng ~3~ có tổng là ~4 + 5 + 6 = 15~. Cột ~1~ có tổng là ~1 + 7 + 4 = 12~. Ô giao nhau tại dòng ~3~, cột ~1~ có giá trị là 4. Tổng cần tìm là: ~15+ 12 - 4 = 23~. Kết quả chia dư cho ~2026~ vẫn là ~23~.

Ràng buộc

• Có ~30%~ số test tương ứng với ~30%~ số điểm của bài thỏa mãn: ~N~ ~\le~ ~10~;
• ~30%~ số test khác tương ứng với ~30%~ số điểm của bài thỏa mãn: ~N~ ~\le~ ~10^5~;
• ~40%~ số test còn lại tương ứng với ~40%~ số điểm của bài thỏa mãn: Không có ràng buộc nào thêm (tức là ~N~ ~\le~ ~10^8~).

Yêu cầu

Xét dãy số tự nhiên từ ~1~ đến ~N~: ~1, 2, 3, 4, 5, 6, ..., N~. Ta biến đổi từng số trong dãy theo quy tắc sau:

• Nếu số đó là số lẻ thì giữ nguyên.
• Nếu số đó là số chẵn thì chia cho ~2~ liên tiếp cho đến khi nhận được một số lẻ, rồi dừng lại.

Ví dụ:

• ~1~ ~\rightarrow~ ~1~
• ~2~ ~\rightarrow~ ~1~
• ~4~ ~\rightarrow~ ~2~ ~\rightarrow~ ~1~
• ~6~ ~\rightarrow~ ~3~
• ~12~ ~\rightarrow~ ~6~ ~\rightarrow~ ~3~
• ~40~ ~\rightarrow~ ~20~ ~\rightarrow~ ~10~ ~\rightarrow~ ~5~

Cho số tự nhiên ~N~. Hãy tính tổng các số trong dãy mới sau khi đã biến đổi tất cả các số từ ~1~ đến ~N~.

Input

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

Output

Ghi ra một dòng chứa một số tự nhiên duy nhất là tổng cần tìm.

Ví dụ

Input

6

Output

14

• Giải thích: Dãy từ ~1~ đến ~6~ là: ~1, 2, 3, 4, 5, 6~. Sau khi biến đổi ta được dãy mới là: ~1, 1, 3, 1, 5, 3~. Tổng các số trong dãy là: ~1 + 1 + 3 + 1 + 5 + 3 = 14~.

Input

10

Output

36

• Giải thích: Dãy từ ~1~ đến ~10~ là: ~1, 2, 3, 4, 5, 6, 7, 8, 9, 10~. Sau khi biến đổi ta được dãy mới là: ~1, 1, 3, 1, 5, 3, 7, 1, 9, 5~. Tổng các số trong dãy là: ~1 + 1 + 3 + 1 + 5 + 3 + 7 + 1 + 9 + 5 = 36~.

Ràng buộc

• Có ~30%~ số test tương ứng với ~30%~ số điểm của bài thỏa mãn: ~N~ ~\le~ ~1000~;
• ~30%~ số test khác tương ứng với ~30%~ số điểm của bài thỏa mãn: ~N~ ~\le~ ~10^6~;
• ~40%~ số test còn lại tương ứng với ~40%~ số điểm của bài thỏa mãn: ~N~ ~\le~ ~10^8~.