Grimm's Conjecture

Time limit2sMemory limit128 MB

Summary

Assign to each number in a composite interval a distinct prime divisor, choosing the lexicographically smallest assignment, for many test cases with H up to 10^10.

Level: Hard8 of 10
Topics: Number theory, Math, Greedy
Solved: No attempts yet

Problem

Grimm's conjecture states that whenever you are given a block of consecutive composite numbers, you can assign to each of them a distinct prime that divides it.

Formally, if $n+1, n+2, \dots, n+k$ are all composite, then there exist $k$ distinct primes $p_i$ such that $p_i$ divides $n+i$ . ( $1 \le i \le k$ )

Given an interval $[L, H]$ of consecutive composite numbers, write a program that, for each of $L, L+1, \dots, H$ , finds one distinct prime dividing it.

If several assignments are possible, output the lexicographically smallest one: make the prime assigned to the first number as small as possible; among those, make the prime assigned to the second number as small as possible; then the third, and so on.

Input

The input consists of several test cases. Each test case is a single line with two integers $L$ and $H$ . ( $4 \le L < H \le 10^{10}$ )

Every number in the interval $[L, H]$ is guaranteed to be composite.

The last line contains two zeros and must not be processed.

Output

For each test case, print on one line the prime assigned to each number from $L$ to $H$ , separated by single spaces.

Examples5

Example 1

Input

242 250
8 10
0 0

Expected output

2 3 61 7 41 13 31 83 5
2 3 5

Example 2
Input
```
8 9
0 0
```
Expected output
```
2 3
```
Example 3
Input
```
14 16
0 0
```
Expected output
```
7 3 2
```
Example 4
Input
```
24 28
0 0
```
Expected output
```
2 5 13 3 7
```
Example 5
Input
```
90 96
0 0
```
Expected output
```
2 7 23 31 47 5 3
```