ПИТОН! ОТ Обратное число

В этой задаче нужно ответить на 1≤≤105

1

≤

t

≤

10

5

запросов. Каждый запрос состоит из двух целых чисел 2≤≤109

2

≤

p

≤

10

9

и 0<<

0

<

a

<

p

, число

p

является простым. На каждый запрос нужно вывести в отдельной строке целое число 0<<

0

<

b

<

p

такое, что (⋅−1) ⋮

(

a

⋅

b

−

1

)

⋮

p

.

Входные данные

В первой строке дано целое число

t

— количество запросов.

В следующих

t

строках даны по два числа

p

i

и

a

i

, =1,…,

i

=

1

,

…

,

t

.

Выходные данные

Выведите

t

целых чисел (каждое число в отдельной строке) — ответы на запросы.

Примеры

Ввод

Вывод

4

5 1

5 2

5 3

5 4

1

3

2

4

Ограничения

Время выполнения: 5 секунд