## CERI2018C - Congruent primes

The goal of this problem is to print some prime numbers.

### Input

The first line of the input consist of a single integer number *t* which
determines the number of tests.

In each of next *t* lines there is two integer numbers *a* and *n*.

#### Constraints

- 0 < t ≤ 10 000
- 0 < a ≤ 100 000
- 1 < n ≤ 1 000 000

### Output

For all test cases, print all the prime numbers $p$ such that $0\le p \le 10^7$ and $p\equiv a \pmod n$.

If there are no such prime numbers, print "None" without quotes.

### Example

Input:3 1337 300000 42 12345 42 100001Output:1201337 3601337 7801337 9001337 None 100043 1700059 2500067 4700089 5900101 7100113 8500127 9700139

Added by: | Francky |

Date: | 2018-05-03 |

Time limit: | 60s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All |