Counting Perfect Square Product Subsets

Du Laoshi dreams of participating in the World Finals for an infinite number of years. Although the rules forbid it, he decides to bend them just a little. This year, since the World Finals and THUSC are scheduled so close together, Du Laoshi came up with an idea and then left it aside...

You are given two integers \(L\) and \(R\). Consider the set of integers \(\{L, L+1, \dots, R\}\) (which has \(R-L+1\) elements). Your task is to count the number of different subsets (the empty set is also counted, with its product defined as \(1\)) such that the product of all numbers in the subset is a perfect square.

Note: A number is a perfect square if it can be written as \(k^2\) for some integer \(k\). In particular, the empty set has a product of \(1=1^2\), so it is considered valid.

Hint: Every number \(x\) can be represented as \(x=s^2\cdot t\) where \(t\) is square‐free. The product of a subset is a perfect square if and only if, for each square‐free part \(t\neq1\), the total count of numbers with that square‐free part in the subset is even.

Solve the problem by grouping numbers according to their square‐free part. For numbers that are already perfect squares (i.e. whose square‐free part is 1) they do not affect the parity constraint.

inputFormat

The input consists of a single line containing two integers \(L\) and \(R\) separated by a space.

outputFormat

Output one integer: the number of subsets of \(\{L, L+1, \dots, R\}\) whose product is a perfect square.

sample

1 1

2