Interesting Set

Time limit1sMemory limit128 MB

Summary

Given a range [a,b], find the minimum-product square-forming subset using squarefree factorization and linear algebra over GF(2) plus meet-in-the-middle/graph reasoning.

Level: Hard8 of 10
Topics: Number theory, Math, Bit manipulation, Brute force
Solved: No attempts yet

Problem

The numbers $6$ , $10$ , and $15$ are not perfect squares, yet their product $900 = 30^2$ is a perfect square.

A set of positive integers whose elements multiply to a perfect square is called an interesting set. For example, $\{6, 10, 15\}$ and $\{25\}$ are both interesting sets.

The product of all elements of an interesting set is called its value; by definition this value is always a perfect square.

Given a set $S$ , write a program that finds the smallest value among all non-empty subsets of $S$ that are interesting sets.

Input

The input consists of several test cases. Each test case is a single line containing two integers $a$ and $b$ with $1 < a < b \le 4900$ . These two numbers describe the set $S = \{x \in \mathbb{N} \mid a \le x \le b\}$ , where $\mathbb{N}$ is the set of natural numbers. Process every test case until the end of input.

Output

For each test case, let $k^2$ be the smallest value among all non-empty subsets of $S$ that are interesting sets, and print $k$ on its own line. If no non-empty subset is an interesting set, print none instead.

Examples3

Example 1

Input

20 30
101 110
2337 2392

Expected output

5
none
3580746020392020480

Example 2
Input
```
2 10
8 20
5 8
```
Expected output
```
2
3
none
```
Example 3
Input
```
240 245
```
Expected output
```
3780
```