EVENSEMIP - Even Semiprime Runs

no tags 

A semiprime is a product of two primes such as $9 = 3\times3$ or $580519 = 41\times14159$.

The first ten semiprimes are $4$, $6$, $9$, $10$, $14$, $15$, $21$, $22$, $25$, and $26$.

A run of semiprimes is a contiguous subsequence of semiprimes. For example, $15$, $21$, $22$ is a run but $9$, $14$, $15$ is not because it skips over $10$.

An even run of semiprimes is a run that contains only even numbers. The first even run of length $3$ is $454$, $458$, $466$.

Your task is to find the longest even run of semiprimes between $N$ and $M$, inclusive.

Input

The first line contains $T$ ($1 \le T \le 20$), the number of test cases.

Each test case is one line containing the integers $N$ and $M$ ($1 \le N \le M \le 10^{14}$, $M - N \le 10^7$).

The sum of the differences $M - N$ over all test cases is at most $10^7$.

Output

Print two lines per test case. On the first line, print the length of the longest even run of semiprimes. On the second line, print the numbers in the run.

If there are multiple solutions, print the one with the smallest first number.

It is guaranteed that there is at least one even semiprime between $N$ and $M$.

Example

Input:
16
4 4
4 6
4 8
4 14
6 10
58 62
1 100
1 1000
1 10000
1 100000
1 1000000
5000000 10000000
247425787142 247425787222
247425000000 247425787221
466937174866 466937199999
99999999000000 100000000000000

Output:
1
4
2
4 6
2
4 6
2
4 6
1
6
2
58 62
2
4 6
3
454 458 466
3
454 458 466
3
454 458 466
5
111614 111626 111634 111638 111646
5
5161318 5161322 5161334 5161342 5161346
8
247425787142 247425787162 247425787166 247425787174 247425787178 247425787198 247425787214 247425787222
7
247425787142 247425787162 247425787166 247425787174 247425787178 247425787198 247425787214
4
466937176054 466937176058 466937176066 466937176078
4
99999999199498 99999999199502 99999999199522 99999999199558

Note

This problem was inspired by Zak Seidov's post in the SeqFan mailing list.



hide comments
julkas: 2018-08-11 13:16:57

@traxexeuler Good, interesting problem. What's your timing? And what is maximum even/odd semiprime runs up to 10**14?

Last edit: 2018-08-11 15:04:53

Added by:traxex
Date:2018-04-23
Time limit:20s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:SeqFan mailing list