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 100001
Output:
1201337 3601337 7801337 9001337 
None
100043 1700059 2500067 4700089 5900101 7100113 8500127 9700139 

hide comments
weathervane: 2020-08-23 22:47:36

@francky thank you, I misunderstood the question.

Last edit: 2020-08-24 11:47:53
weathervane: 2020-08-23 19:47:43

@francky I don't get why my answers are wrong. I've made a large number of test case files solved by a simple slow and brutal method, to verify my optimised solution. Every answer is submitted twice, once with a space at the end of a "numbers" line as shown, and one without.
=(Francky)=> Your brute force solution should be checked again, you have many wrong answers. Judge ignore extra whitespace, so both methods will be accepted once you have solved your issue. Good luck.

Last edit: 2020-08-23 22:24:17

Added by:Francky
Date:2018-05-03
Time limit:60s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All