Sau khi hoàn thành hành trình khám phá toàn bộ Việt Nam, vì do lười nên PhuocThien và Prototype dừng lại, chỉ còn hai người tiếp tục cuộc hành trình. ledinhbaonam và uia quyết định tiếp tục chuyến đi sang Lào — đất nước thứ hai trong hành trình vòng quanh thế giới.

Sau nhiều ngày băng qua các khu rừng nguyên sinh và những dãy núi phủ đầy sương mù, cả nhóm vô tình phát hiện một thư viện cổ đại bị chôn vùi sâu dưới lòng đất.

Tại trung tâm thư viện là một phiến đá khổng lồ chứa một dãy số bí ẩn:

Theo những ký tự cổ mà uia giải mã được, nền văn minh này tin rằng trong dãy số tồn tại những “đoạn năng lượng tối thượng” — những đoạn có thể kích hoạt cánh cổng dẫn tới kho báu cuối cùng của thư viện.

Nhiệm vụ

• Tìm tất cả các đoạn năng lượng tối thượng trong dãy, biết để một đoạn được công nhận là đoạn năng lượng tối thượng, nó phải thỏa mãn đồng thời các điều kiện sau:
  • Tất cả các phần tử trong đoạn có cùng số lượng ước nguyên dương.
  • Độ dài đoạn là một số nguyên tố.
  • Hiệu giữa phần tử lớn nhất và nhỏ nhất trong đoạn không vượt quá \(k\).
  • Giá trị XOR của toàn bộ đoạn là một số nguyên tố.

Input

• Dòng đầu chứa hai số nguyên \(n,k\) (\(1 \le n \le 2 \times 10^5,\ 0 \le k \le 10^6\))
• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,\dots,a_n\) (\(1 \le a_i \le 10^6\))

Output

• In ra số lượng đoạn con hợp lệ.

Example

6 5
2 3 5 4 9 25

1

24 12
2 3 5 7 11 13 4 9 25 49 8 27 16 81 17 19 23 29 31 37 121 169 289 361

5