F. Квадратичные прыжки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны два целых числа $$$n$$$ и $$$q$$$. Рассмотрим граф с $$$n$$$ вершинами, в котором вершины $$$i$$$ и $$$j$$$ соединены ребром тогда и только тогда, когда $$$|j - i|$$$ является полным квадратом$$$^{\text{∗}}$$$.

Вам даны $$$q$$$ пар чисел $$$a_i, b_i$$$. Необходимо для каждой из этих $$$q$$$ пар найти кратчайшее расстояние между вершинами $$$a_i$$$ и $$$b_i$$$ в данном графе. Можно доказать, что граф связен, поэтому расстояние между $$$a_i$$$ и $$$b_i$$$ не равно бесконечности.

$$$^{\text{∗}}$$$Целое число $$$x$$$ является полным квадратом, если существует целое число $$$y$$$, такое что $$$x = y^2$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le q \le 10^5$$$) — количество вершин в графе и количество пар вершин, между которыми нужно найти расстояние.

Затем в следующих $$$q$$$ строках идет описание пар вершин, для которых нужно найти кратчайшее расстояние. Каждая из пар описывается двумя числами $$$a, b$$$ ($$$1 \leq a \lt b \leq n$$$) — номера вершин, между которыми нужно найти кратчайшее расстояние.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$, и что сумма $$$q$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

Для каждого набора входных данных выведите для каждой из $$$q$$$ пар вершин кратчайшее расстояние между ними.

Пример
Входные данные
2
5 4
1 2
1 3
1 4
1 5
8 3
3 7
2 5
1 7
Выходные данные
1
2
2
1
1
2
3
Примечание

Так выглядит граф для первого набора входных данных:

  • Для первой пары вершин кратчайший путь $$$1 \rightarrow 2$$$.
  • Для второй пары вершин кратчайший путь $$$1 \rightarrow 2 \rightarrow 3$$$.
  • Для третьей пары вершин кратчайший путь $$$1 \rightarrow 5 \rightarrow 4$$$.
  • Для четвертой пары вершин кратчайший путь $$$1 \rightarrow 5$$$.

Так выглядит граф для второго набора входных данных:

  • Для первой пары вершин кратчайший путь $$$1 \rightarrow 2$$$.
  • Для второй пары вершин кратчайший путь $$$2 \rightarrow 6 \rightarrow 5$$$.
  • Для третьей пары вершин кратчайший путь $$$1 \rightarrow 2 \rightarrow 6 \rightarrow 7$$$.