Bạc là một người nông dân lâu đời, sống trên một vùng đất rộng lớn mà tổ tiên để lại. Mảnh đất của Bạc là một khu vực hình vuông với diện tích rất đẹp. Tuy nhiên, sau mùa dịch kéo dài, tài chính của Bạc gặp nhiều khó khăn, và ông quyết định bán một phần đất để trang trải cuộc sống. Bạc muốn bán đất theo từng mảnh vuông vức để thuận tiện trong việc phân lô và giao dịch.

Bạc có thể chọn bán các mảnh đất hình vuông với nhiều kích thước khác nhau: từ những ô đất nhỏ nhất có kích thước ~1×1~, cho đến các khu đất lớn hơn như ~2×2, 3×3, ...,~ hoặc thậm chí là cả mảnh đất ~N×N~ nếu cần thiết. Bây giờ, Bạc muốn biết có bao nhiêu cách chọn một mảnh đất hình vuông từ mảnh đất ban đầu để có thể tính toán phương án bán hợp lý nhất. Bạn có thể giúp Bạc tìm ra số cách chọn này không?

Input

• Một số nguyên dương ~N~ là chiều dài mỗi cạnh của mảnh đất (~N \leq 10^{18}~).

Output

• Gồm một số nguyên duy nhất là số phương án chọn cách bán đất sau khi chia lấy dư cho ~12345678987654321~.

Sample Input

3

Sample Output

14

Notes

Giải thích cách đếm:

• Có ~9~ cách chọn mảnh đất kích thước ~1×1~.
• Có ~4~ cách chọn mảnh đất kích thước ~2×2~.
• Có ~1~ cách chọn mảnh đất kích thước ~3×3~.
• Tổng cộng: ~9 + 4 + 1 = 14~ cách.

Sau khi đất của Bạc bị chiếm dụng, Lê quyết định sử dụng các viên bột đá ép thành hình vuông đơn vị để tạo ra những viên gạch lát chất lượng cao. Tuy nhiên, để quảng bá sản phẩm, Lê muốn làm ra các viên đá lát với kích thước khác nhau, mỗi viên là một hình vuông có cạnh khác nhau, chẳng hạn ~1×1, 2×2, 3×3, ...~. Không nhất thiết phải sử dụng hết các viên đơn vị có sẵn, nhưng mục tiêu của Lê là tạo ra số lượng sản phẩm nhiều nhất có thể để trưng bày. Mỗi viên đá lát hình vuông kích thước ~k×k~ cần ~k^2~ viên đơn vị. Với ~N~ viên đơn vị hiện có, bạn hãy xác định số lượng viên gạch (mỗi viên có kích thước khác nhau) mà Lê có thể làm ra, sao cho tổng số viên đơn vị cần dùng không vượt quá ~N~.

Input

• Một dòng chứa duy nhất số nguyên dương ~N~ ~(N \leq 10^{18})~.

Output

• Một số nguyên duy nhất là số lượng sản phẩm tối đa mà Lê có thể tạo ra.

Sample Input

15

Sample Output

3

Giải thích

• Có thể làm được ~1~ viên ~1×1~, ~1~ viên ~2×2~ và ~1~ viên ~3×3~ với tổng ~1 + 4 + 9 = 14 ≤ 15~. Việc làm viên ~4×4~ đòi hỏi ~16~ viên, vượt quá ~N~.

Vì Lê và Bạc đã bàn xôn xao về chuyện mua gạch, bán đất rất dữ dội, nên sau khi biết tin Kiên - một đại gia chơi đất đã rất muốn thể hiện sự giàu có của mình bằng cách phát tặng ~N~ mảnh đất hình chữ nhật có chiều rộng là ~a_i~ và chiều dài là ~b_i~ cho mọi người . Do còn nhiều người muốn xin đất của Kiên nên bạn chỉ được phép chọn 1 mảnh đất trong ~N~ mảnh đất đó. Nhưng mà, đời không như là mơ, không ai cho không bạn thứ gì cả và Kiên cũng vậy, Kiên nói là muốn lấy đất của Kiên thì phải đạt một trong các điều kiện sau thì mới có thể lấy đất .

• Điều kiện ~1~: Chiều dài của mảnh đất phải chia hết cho chiều rộng ,thoả mản chiều dài mảnh đất là số siêu nguyên tố, khi đó bạn có thể nhận được mảnh đất đó, nhưng điều quan trọng là bạn cần tìm mảnh đất có diện tích lớn nhất và thoả mãn điều kiện trên .

• Điều kiện ~2~: Bạn chỉ được phép lấy mảnh đất có chiều dài và chiều rộng đều là số nguyên tố, khi đó bạn có thể nhận mảnh đất đó, nhưng Kiên lại không thích điều kiện này nên chỉ cho bạn mảnh đất thoả mãn điều kiện trên và có diện tích là nhỏ nhất .

• Điều kiện ~3~: Bạn không lấy đất thì bạn không có điều kiện và diện tích bạn nhận được là ~0~.

• Lưu ý: Theo cấp bậc nếu thoả mãn điều kiện ~1~ thì không được sử dụng các điều kiện còn lại, nếu không thoả mãn thì tăng loại điều kiện lên .

• Số siêu nguyên tố ở đây định nghĩa là số đó là nguyên tố là khi bỏ các số từ phải sang trái vẫn là số nguyên tố . Ví dụ số ~17~ ở đây không được gọi là số siêu nguyên tố vì ~17~ xoá ~7~ còn ~1~ không nguyên tố, nhưng ~23~ là số siêu nguyên tố vì ~23~ xoá ~3~ còn ~2~ vẫn nguyên tố.

Input

• Dòng 1 : Gồm số nguyên ~N~ ~(N \leq 10^5)~.
• Dòng 2 : Gồm ~N~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(a_i \leq 10^6)~
• Dòng 3 : Gồm ~N~ số nguyên dương ~b_1, b_2, ..., b_n~ ~(b_i \leq 10^6)~

Output

• Gồm một số nguyên là diện tích đất có thể lấy .

Sample Input 1

6
7 2 2 7 2 11
11 3 5 2 23 2

Sample Output 1

6

Sample Input 2

6
79 3 2 23 7 11
97 2 5 23 2 2

Sample Output 2

529

Note

• Ví dụ ~1~ : Chọn mảnh đất thứ ~2~ thoả mản điều kiện ~2~ có diện tích : ~2*3=6~ .
• Ví dụ ~2~ : Chọn mảnh đất thứ ~4~ thoả mản điều kiện ~1~ có diện tích : ~23*23=529~ .

Trong một cuộc hành trình khám phá những con số kỳ diệu, bạn được giao nhiệm vụ tìm ra "dãy con đơn điệu" từ một dãy số nguyên dương. Một dãy con được gọi là đơn điệu nếu các phần tử trong nó là một tập hợp con của dãy, không nhất thiết phải liên tiếp nhưng phải giữ nguyên thứ tự của dãy ban đầu. Nhiệm vụ của bạn là đếm số lượng dãy con đơn điệu sao cho tổng các phần tử trong dãy con đó chính xác bằng một số nguyên dương cho trước ~S~. Qua đó, bạn sẽ khám phá ra bao nhiêu "mảnh ghép" ẩn chứa giá trị bí ẩn ~S~ trong dãy số.

Input

• Dòng đầu: chứa hai số nguyên dương ~N~ và ~S~ ~(N \leq 100, S \leq 10^5)~.
• Dòng sau: chứa ~N~ số nguyên dương là các số trong dãy có giá trị không vượt quá ~10^5~.

Output

• In ra một số nguyên duy nhất là số lượng dãy con đơn điệu có tổng đúng bằng ~S~.

Sample Input

5 5
1 2 3 4 5

Sample Output

3

Note

• Các dãy con thỏa mãn là: ~(1,4)~, ~(2,3)~, ~(5)~.