Số đẹp là số có tổng bình phương các chữ số của nó (trong dạng biểu diễn thập phân) là một số nguyên tố. Ví dụ: 23 là một số đẹp vì ~2^2~  +  ~3^2~ là một số nguyên tố.

Dãy các số đẹp lần lượt là: 11, 12, 14, 16, 21, 23, 25, 27, 32, 38, ... . Các số đẹp được đánh số thứ tự tăng dần theo giá trị bắt đầu số thứ nhất là 11 , số thứ hai là 12, ...,  số thứ mười là 38.

Yêu cầu: Cho số nguyên dương ~N~ . Hãy tìm số đẹp thứ ~N~.

Input

• Chứa duy nhất một số nguyên ~N~ (~1 ≤ N ≤ 10000~).

Output

• Số đẹp thứ ~N~.

Scoring

• Subtask 1 (70%): ~N ≤ 10~;

• Subtask 2 (30%): Không ràng buộc gì thêm.

Examples

Input

1

Output

11

Input

6

Output

23

Cho mảng ~A~ gồm ~n~ số ~0~ và ~q~ truy vấn dạng (~l,r~), tăng các phần tử ~A_l,A_l+1,…,A_r~ lên ~1~ đơn vị.

Input

• Dòng đầu tiên gồm 2 số nguyên ~n~,~q~.
• ~q~ dòng tiếp theo mỗi dòng gồm 2 số nguyên ~l~,~r~.

Output

• In ra mảng ~A~ sau ~q~ truy vấn.

Điều kiện

~1 ≤ n,q ≤ 10^5~.~1≤l,r≤n~.

Ví dụ

Input:

4 3
1 3
2 4
1 2

Output:

2 3 2 1

Cho ~N~ bình chứa nước lần lượt có thể tích là các số ~a_1.. a_N~. Khi xếp các bình theo một dãy thì sẽ tạo thành 1 khối. Nếu xếp lần lượt các bình chứa nước theo trình tự đó thì thể tích cả khối là ~a_1 + a_2 + ... + a_N + max(0, a_2 - a_1) + max(0, a_3 - a_2) + ... + max(0,a_N - a_{N - 1}~. Nhiệm vụ của bạn là tìm cách xếp sao cho tổng thể tích chứa của cả khối là lớn nhất có thể.

Dữ liệu:

• Dòng đầu ghi số nguyên dương ~N~ (~0 < n ≤ 10^5~).
• ~N~ dòng sau mỗi dòng ghi một số ~a_i~ ( ~1 ≤ i ≤ N và 1 ≤ a_i ≤ 10000~).

Kết quả:

• Ghi trên một dòng kết quả là thể tích lớn nhất tìm được.

Ví dụ

Input

4
5 4 1 7

Output

24

Trong một dây chuyển sản xuất tự động có ~n~ cánh tay ROBOT được đánh số từ ~1~ đến ~n~, các cánh tay ROBOT này phải hoàn thành ~n~ công việc theo thứ tự đã được đánh số.

Thời gian hoàn thành độc lập công việc của cánh tay thứ ~i~ là ~t_i~ giây. Nếu cánh tay thứ i và thứ ~i + 1~ phối hợp thì thời gian làm xong việc cho cả hai là ~p_i~ giây.

Yêu cầu: Viết chương trình tìm phương án sao cho công việc đều hoàn thành với tổng thời gian ít nhất.

Input

• Dòng đầu tiên ghi số tự nhiên n (~1 ≤ n ≤ 10^6~).

• Dòng thứ hai ghi n số ~t~ (~1 ≤ t_i ≤ 60, 1 ≤ i ≤ n~).

• Dòng thứ ba ghi ~n - 1~ số ~p_i~ (~1 ≤ p_i ≤ 100~).

Output

• Dòng đầu tiên ghi tổng thời gian ít nhất để hoàn thành công việc.

Example

Input

5
2 5 7 8 4
4 9 10 10

Output

18

Xét tất cả các số nguyên được tạo bởi một dãy liên tiếp các chữ số của ~C~, với mỗi số, An kiểm tra xem số đó có phải là số nguyên tố hay không và tự hỏi trong tất cả các số nguyên được xét, có bao nhiêu số nguyên tố? Là một lập trình viên tài ba, bạn hãy giúp An nhé!

Dữ liệu vào

• Số nguyên C (~0 ≤ C ≤ 2 × 10^9~).

Dữ liệu ra

• Ghi ra số lượng các số nguyên tố tìm được. Nếu không có thì in ra thông báo "NO PRIMES"

Ví dụ

Input

2319

Output

5