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