Số chính phương đặc biệt là số chính phương được tạo bởi một số nguyên tố. Ví dụ ~4 = 2 \times 2; \ 9 = 3 \times 3; \ 36 = 6 \times 6~ nên ~4~ và ~9~ là số chính phương đặc biệt còn ~36~ thì không phải là số chính phương đặc biệt.

Yêu cầu: Cho ~2~ số nguyên dương ~a, b~. Hãy đếm xem trong đoạn ~[a..b]~ có bao nhiêu số chính phương đặc biệt?

Dữ liệu vào từ tệp văn bản CP.INP:

Gồm hai số nguyên dương ~a, b \ (2 \le a \le b \le 10^{12})~.

Kết quả ghi ra tệp văn bản CP.OUT:

Gồm một dòng chứa một số duy nhất là kết quả của bài toán.

Ràng buộc

• Có ~80\%~ số test ứng với ~80\%~ số điểm của bài thoả mãn ~2 \le a \le b \le 10^6;~
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

2 10

Output

2

Cho một bảng ô vuông gồm ~n~ hàng và ~n~ cột. Các hàng được đánh số từ ~1~ đến ~n~, các cột được đánh số từ ~1~ đến ~n~. Ô ở hàng thứ ~i~ và cột thứ ~j~ có giá trị là ~i \times j~ ~(1 \le i \le n, \ 1 \le j \le n)~.

Yêu cầu: Cho một số nguyên dương ~x~. Hãy đếm số lượng ô trong bảng có giá trị bằng ~x~.

Dữ liệu vào từ tệp văn bản BS.INP:

Gồm hai số nguyên ~n~ và ~x~ ~(1 \le n \le 10^6, \ 1 \le x \le 10^{12})~ là kích thước của bảng và số nguyên ta cần tìm trong bảng.

Kết quả ghi ra tệp văn bản BS.OUT:

Số nguyên duy nhất là số lượng ô trong bảng có giá trị bằng ~x~.

Ràng buộc

• Có ~70\%~ số test ứng với ~70\%~ số điểm của bài thoả mãn ~0 \lt n \le 10^3, \ 1 \le x \le 10^6;~
• ~30\%~ số test còn lại ứng với ~30\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

6 5

Output

2

Input

6 12

Output

4

Input

5 13

Output

0

Giải thích

Nhờ hoàn thành tốt công việc, An và Bình được công ty thưởng ~N~ tờ tiền. Tờ tiền thứ ~i~ có mệnh giá ~a_i~. Hai bạn muốn chia đôi số tiền thành hai phần bằng nhau bằng cách chia cho mỗi người một số tờ tiền. Vì thế hai bạn quyết định sẽ chọn ra những tờ tiền để tổng số tiền hai bạn nhận được bằng nhau và lớn nhất, phần còn lại (nếu có) sẽ đem đi đầu tư.

Yêu cầu: Hãy giúp hai bạn tính tổng số tiền lớn nhất mà mỗi người nhận được trước khi đầu tư.

Dữ liệu vào từ tệp văn bản CT.INP:

• Dòng đầu tiên chứa số nguyên dương ~N \ (N \le 500);~
• Dòng thứ hai bao gồm ~N~ số nguyên dương ~a_1, a_2, ..., a_N~ là mệnh giá của những tờ tiền. Tổng giá trị những tờ tiền sẽ không vượt quá ~10^5~.

Kết quả ghi ra tệp văn bản CT.OUT:

Gồm một dòng duy nhất là số tiền lớn nhất mà mỗi người nhận được.

Ràng buộc

• Có ~40\%~ số test ứng với ~40\%~ số điểm của bài thoả mãn ~N \le 3;~
• ~30\%~ số test tiếp theo ứng với ~30\%~ số điểm của bài thoả mãn ~N \le 12;~
• ~30\%~ số test còn lại ứng với ~30\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

5
1 2 4 5 2

Output

7

Giải thích:

• An có thể chọn những tờ tiền có mệnh giá ~1, 2, 4~.
• Bình chọn những tờ tiền còn lại có mệnh giá ~5, 2~.
• Mỗi người sẽ nhận được tổng số tiền là ~7~. Vì số tiền mỗi người nhận đã bằng nhau và đã chia hết số tiền nên họ sẽ không đầu tư.

Input

5
9 8 4 5 13

Output

17

Giải thích:

• An sẽ chọn những tờ tiền có mệnh giá ~9, 8~.
• Bình sẽ chọn những tờ tiền có mệnh giá ~4, 13~.
• Mỗi người sẽ nhận được tổng số tiền là ~17~. Tờ tiền còn lại có mệnh giá ~5~ sẽ đem đi đầu tư.

Ban quản lý rừng nguyên sinh đang quản lý một khu vực rộng lớn. Họ đã xây dựng ~N~ trạm canh gác rừng (được đánh số từ ~1~ đến ~N~) và các trạm này được kết nối với nhau bởi ~M~ con đường. Trong ~N~ trạm canh gác người ta đã chọn ra ~K~ trạm làm trạm gác trung tâm - nơi điều hành các trạm gác nhỏ hơn và chứa các dụng cụ, phương tiện bảo về rừng. Để đi lại và vận chuyển thiết bị dễ dàng giữa các trạm gác trung tâm, Ban quản lý quyết định nâng cấp một số con đường sao cho ~K~ trạm gác trung tâm đều đi được đến nhau.

Yêu cầu: Hãy chọn các con đường nối ~K~ trạm gác trung tâm để nâng cấp sao cho tổng độ dài các con đường này là nhỏ nhất.

Dữ liệu vào từ tệp văn bản TG.INP:

• Dòng đầu tiên ghi ba số nguyên dương ~N, M, K~ lần lượt là số lượng các trạm gác, số các con đường nối giữa các trạm gác và số lượng các trạm gác trung tâm ~(1 \le N \le 500; \ N-1 \le M \lt \dfrac{N^2}{2}; \ 1 \lt K \le N);~
• Dòng thứ hai ghi ~K~ số nguyên là số hiệu của ~K~ trạm gác trung tâm~;~
• Trong ~M~ dòng tiếp theo, mỗi dòng ghi ba số nguyên ~u, v, c~ với ý nghĩa con đường hai chiều nối trực tiếp giữa hai trạm ~u~ và ~v~ có độ dài là ~c~ ~(1 \lt c \le 10^9).~

Kết quả ghi ra tệp văn bản TG.OUT:

Một dòng duy nhất chứa tổng độ dài các con đường thoả mãn yêu cầu trên.

Ràng buộc

• Có ~40\%~ số test ứng với ~40\%~ số điểm của bài thoả mãn: ~K = N, \ N \le 500;~
• ~30\%~ số test tiếp theo ứng với ~30\%~ số điểm của bài thoả mãn: ~K \le 10, \ N \le 200;~
• ~30\%~ số test còn lại với ~30\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

5 8 3
1 3 5
1 2 2
1 3 10
1 4 12
2 4 5
2 5 7
3 4 2
3 5 10
4 5 6

Output

15

Giải thích

Cần làm các con đường:

1 2
2 4
3 4
4 5

Tổng độ dài nhỏ nhất là: ~15~.

Cho số nguyên dương ~N~ và dãy hoán vị từ ~1~ đến ~N~. Hãy tính tổng chi phí nhỏ nhất để sắp xếp dãy hoán vị ban đầu thành dãy tăng dần. Biết rằng có thể chọn một dãy con liên tiếp từ ~i~ đến ~j~ và sắp xếp lại dãy con này thành dãy tăng dần với chi phí là ~\lfloor \sqrt {j - i + 1} \rfloor~ (lấy phần nguyên, ví dụ ~\lfloor 10,3333 \rfloor = 10~).

Dữ liệu vào từ tệp văn bản SX.INP:

• Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \leq N \leq 10^6~);
• Dòng thứ hai chứa ~N~ số nguyên dương là hoán vị từ ~1~ đến ~N~.

Kết quả ghi ra tệp văn bản SX.OUT:

Chi phí nhỏ nhất để sắp xếp dãy hoán vị đã cho thành dãy tăng dần.

Ràng buộc

• Có ~30\%~ số test ứng với ~30\%~ số điểm của bài thoả mãn ~N \leq 9;~
• ~30\%~ số test tiếp theo ứng với ~30\%~ số điểm của bài thoả mãn ~N \leq 2000;~
• ~30\%~ số test tiếp theo ứng với ~30\%~ số điểm của bài thoả mãn ~N \leq 10^5;~
• ~10\%~ số test còn lại ứng với ~10\%~ số điểm của bài thoả mãn ~N \leq 10^6.~

Ví dụ

Input

5
3 1 4 2 5

Output

2

Giải thích

Chọn dãy con ~[3, 1]~ mất chi phí ~1~ và chuyển dãy thành ~[1, 3, 4, 2, 5]~, sau đó chọn dãy con ~[3, 4, 2]~ với chi phí ~1~ để sắp xếp thành dãy ~[1, 2, 3, 4, 5]~ với tổng chi phí là ~2~.