Hành tinh đặc biệt

Trong một hành tinh cổ đại thuộc hệ sao Zerith, các nhà toán học thiên văn đã phát hiện một bảng dữ liệu cổ được cho là chứa những cặp tọa độ liên hành tinh quan trọng. Tuy nhiên, chỉ những cặp tọa độ nào có chung nguồn gốc năng lượng nguyên thủy mới được coi là cặp số may mắn và đáng được phân tích sâu hơn.

Có thể xem tọa độ của mỗi hành tinh là một số nguyên dương \(x \leq 10^7\). Hai hành tinh khác nhau sẽ mang hai tọa độ khác nhau. Có thể biết rằng trong vũ trụ này chỉ có tối đa \(10^7\) hành tinh khác nhau. Hành tinh mang tọa độ \(x\) và hành tinh mang tọa độ y được gọi là phù hợp với nhau khi và chỉ khi \(x\) và \(y\) có chung tập ước nguyên tố. Ví dụ, \(x = 6\) và \(y = 18\) được gọi là phù hợp với nhau vì tập ước nguyên tố của \(6\) là \(\{2, 3\}\), tập ước nguyên tố của \(18\) là \(\{2, 3\}\). Tuy nhiên, với \(x = 5\) và \(y = 10\) không được gọi là phù hợp với nhau vì tập ước nguyên tố của \(5\) là \(\{5\}\) và tập ước nguyên tố của \(10\) là \(\{2, 5\}\).

Các nhà toán học thiên văn được giao nhiệm vụ, nhiệm vụ này mang hai số nguyên dương \(L, R\) \((1 \leq L \leq R \leq 10^7)\), yêu cầu các nhà thiên văn xác định được số lượng cặp hành tinh \((u, v)\) sao cho \((L \leq u < v \leq R)\), \(u\) và \(v\) phù hợp với nhau. Bạn hãy giúp các nhà toán học thiên văn giải quyết nhiệm vụ này nhé !

Input

Một dòng duy nhất là hai số nguyên dương \(L\) và \(R\) \((1 \leq L \leq R \leq 10^7)\) - hai con số xác định nhiệm vụ của các nhà toán học thiên văn.

Output

Một dòng duy nhất là số lượng cặp \((u, v)\) - yêu cầu xác định của nhiệm vụ được giao.

Example

1 10

4

Scoring

• Có \(20\%\) số test tương ứng với \(20\%\) số điểm có \(1 \leq L \leq R \leq 10^2\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm có \(1 \leq L \leq R \leq 10^3\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm có \(1 \leq L \leq R \leq 10^5, R - L + 1 \leq 10^4\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm có \(1 \leq L \leq R \leq 10^6\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm có \(1 \leq L \leq R \leq 10^7\).