Hộp Quà Bí Ẩn là một món hàng thú vị khi mua sắm trên các chợ trực tuyến. Cửa hàng Huy cũng đang bán mặt hàng này. Cửa hàng đã nhập về ~N~ món hàng, với món hàng thứ ~i~ có giá ~A_i~.

Mỗi hộp quà bí ẩn do cửa hàng chọn sẽ bao gồm 3 món hàng, sao cho độ chênh lệch giá giữa món đắt nhất và món rẻ nhất trong ba món được chọn không vượt quá ~d~.

Nhiệm vụ: Hãy giúp cửa hàng đếm số cách khác nhau để chọn ra một hộp quà bí ẩn. Hai cách chọn được coi là khác nhau nếu tồn tại ít nhất một món hàng có trong cách chọn này nhưng không có trong cách chọn kia.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~d~ (~0 ≤ d ≤ 10^6~);
• Dòng thứ hai chứa dãy số nguyên ~A_1, A_2, ..., A_N~ (~1 ≤ A_i ≤ 10^6~). Các số được ngăn cách bởi dấu cách.

Dữ liệu ra:

• Một số nguyên duy nhất biểu thị số cách chọn có thể.

Ví dụ nhập

5 3  
6 1 7 2 4

Ví dụ xuất

2

Ghi chú:

Có hai cách chọn hợp lệ:

• ~{1, 2, 4}~
• ~{4, 6, 7}~

Giới hạn:

• ~60%~ số test ứng với ~1 ≤ N ≤ 200~ và ~A_i ≤ A_{i+1}~ với ~1 ≤ i < N~;
• ~20%~ số test ứng với ~1 ≤ N ≤ 10^4~;
• ~20%~ số test ứng với ~1 ≤ N ≤ 2 × 10^6~.

Cho một mảng ~A~ gồm ~N~ số nguyên tố: ~A_1, A_2, ..., A_N~, một số đẹp được định nghĩa là số chia hết cho ít nhất một số nguyên tố trong mảng ~A~.

Nhiệm vụ: Với số nguyên ~N~ và mảng ~A~, hãy đếm số lượng số đẹp không vượt quá ~M~.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ (~1 ≤ N ≤ 20~);
• Dòng thứ hai chứa dãy số nguyên ~A_1, A_2, ..., A_N~. Các số được ngăn cách bởi dấu cách.

Dữ liệu ra:

• Một số nguyên duy nhất biểu thị số lượng số đẹp.

Ví dụ nhập

2 11  
3 5

Ví dụ xuất

5

Ghi chú

• Các số đẹp là: ~3, 5, 6, 9, 10~.

Giới hạn

• ~60%~ số test ứng với ~1 ≤ M ≤ 10^6~, ~1 ≤ A_i ≤ 10^5~;
• ~20%~ số test ứng với ~1 ≤ M ≤ 10^9~, ~10^5 < A_i ≤ 10^9~;
• ~20%~ số test ứng với ~1 ≤ M ≤ 10^{18}~, ~1 ≤ A_i ≤ 10^{18}~.

Hùng là một học sinh xuất sắc trong lĩnh vực khoa học máy tính và rất hứng thú với việc nghiên cứu các con số trong toán học. Một ngày nọ, sau khi học về số nguyên tố trong lớp, Hùng nhận ra rằng có những số nguyên tố mà khi bình phương lên, tổng các chữ số của kết quả lại là một số nguyên tố mới. Những số này được gọi là số nguyên tố hoàn hảo, còn những số nguyên tố khác (những số mà tổng chữ số của bình phương không phải là số nguyên tố) được gọi là số nguyên tố không hoàn hảo.

Khi về nhà, Hùng nhanh chóng mở máy tính để khám phá về những con số này. Tuy nhiên, khi bật máy, cậu bất ngờ thấy một dãy ~N~ số nguyên dương lạ (gọi là dãy ~A~) trong một thư mục trên máy tính. Lúc này, Hùng muốn biết trong dãy có bao nhiêu số nguyên tố hoàn hảo và bao nhiêu số nguyên tố không hoàn hảo.

Nhiệm vụ: Hãy giúp Hùng xử lý thông tin này.

Dữ liệu vào

• Dòng đầu tiên chứa số ~N~, là độ dài của dãy.
• Dòng thứ hai chứa dãy ~A~ gồm ~N~ số nguyên dương.

Dữ liệu ra

• In ra hai số nguyên: số lượng số nguyên tố hoàn hảo và số lượng số nguyên tố không hoàn hảo, cách nhau một dấu cách.

Ví dụ nhập

5  
9 7 11 13 5

Ví dụ xuất

2 2

Ghi chú

• ~7~ là số nguyên tố hoàn hảo vì ~7^2 = 49~, tổng các chữ số là ~4 + 9 = 13~, là số nguyên tố.
• ~11~ là số nguyên tố không hoàn hảo vì ~11^2 = 121~, tổng các chữ số là ~1 + 2 + 1 = 4~, không phải số nguyên tố.
• ~13~ là số nguyên tố không hoàn hảo vì ~13^2 = 169~, tổng các chữ số là ~1 + 6 + 9 = 16~, không phải số nguyên tố.
• ~5~ là số nguyên tố hoàn hảo vì ~5^2 = 25~, tổng các chữ số là ~2 + 5 = 7~, là số nguyên tố.

Giới hạn

• ~50%~ số test có ~N ≤ 5 \times 10^3~ và ~A_i ≤ 10^4~.
• ~40%~ số test có ~N ≤ 5 \times 10^5~ và ~A_i ≤ 10^7~.
• ~10%~ số test có ~N ≤ 10^6~ và ~A_i ≤ 10^8~.

Jack - J97 là một cậu bé yêu thích lập trình và cũng rất đam mê kiến trúc phương Tây, vì những công trình này thường có tính đối xứng, với các hoa văn giống nhau ở cả bên trái và bên phải. Jack thường xuyên thích làm các bài toán lập trình, và một ngày nọ, trong lúc luyện tập trên một nền tảng trực tuyến, cậu bắt gặp một bài toán thú vị gắn liền với sở thích của mình. Bài toán có thể được tóm tắt như sau: "Cho ~Q~ truy vấn, mỗi truy vấn gồm hai số nguyên dương ~L~ và ~R~, nhiệm vụ là đếm có bao nhiêu số đối xứng có độ dài chẵn tồn tại trong đoạn ~[L, R]~. Một số đối xứng là số đọc xuôi hay ngược đều giống nhau." Bài toán khá thú vị, vì vậy J97 muốn chia sẻ nó với mọi người, và bây giờ nhiệm vụ của bạn là giải quyết nó.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên ~Q~, là số lượng truy vấn.
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~L~ và ~R~.

Dữ liệu ra

• Với mỗi truy vấn, in ra số lượng số đối xứng có độ dài chẵn trong đoạn ~[L, R]~.

Ví dụ nhập

2  
79 97  
1 100

Ví dụ xuất

1  
9

Ghi chú

• Trong đoạn ~[79, 97]~, số đối xứng duy nhất là ~88~.
• Trong đoạn ~[1, 100]~, các số đối xứng là: ~11, 22, 33, 44, 55, 66, 77, 88, 99~.

Giới hạn

• ~30%~ số test có ~Q ≤ 10^2~ và ~L ≤ R ≤ 10^5~.
• ~40%~ số test có ~Q ≤ 5 \times 10^3~ và ~L ≤ R ≤ 10^9~.
• ~30%~ số test có ~Q ≤ 10^5~ và ~L ≤ R ≤ 10^{12}~.

Sol đang nghiên cứu chức năng sinh học đặc biệt của một loài thực vật có tên là Cây Tuyết trên một hành tinh chưa được đặt tên. Sau nhiều ngày quan sát, Sol nhận thấy rằng kiểu sinh sản của Cây Tuyết khá kỳ lạ. Cụ thể, Cây Tuyết không mọc lên khi gieo hạt. Thay vào đó, khi những điều kiện nhất định được đáp ứng, nó xuất hiện và tồn tại tại một điểm cố định theo một quy luật nào đó, với chiều cao ban đầu là ~a~. Sau một thời gian, nó mọc thêm một Cây Tuyết khác phía trước nó với chiều cao ngẫu nhiên ~b~, rồi tiếp tục mọc thêm nhiều cây khác dựa trên quy tắc sau: "Chiều cao của bất kỳ Cây Tuyết nào luôn bằng trung bình cộng của chiều cao cây phía trước và cây phía sau nó."

Nhiệm vụ: Dựa trên chiều cao đã ghi nhận của hai Cây Tuyết đầu tiên, hãy tính chiều cao của Cây Tuyết thứ ~n~.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên: chiều cao của hai cây đầu tiên ~a~ và ~b~.
• Dòng thứ hai chứa một số nguyên dương ~n~.

Dữ liệu ra

• In ra chiều cao của Cây Tuyết thứ ~n~.

Ví dụ nhập 1

2 3  
4

Ví dụ xuất 1

5

Ví dụ nhập 2

1 2  
3

Ví dụ xuất 2

3

Giới hạn

• ~20%~ số test có ~a, b, n ≤ 10^{18}~.
• ~60%~ số test có ~a, b, n ≤ 10^{10^{4}}~.
• ~20%~ số test có ~a, b, n ≤ 10^{10^{5}}~.