F. Пазл
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам подарили пазл, каждая деталька этого пазла — это квадрат с единичной стороной. На этот пазл можно наклеить любую картинку, разрезать и получить почти привычный пазл.

Ваш друг заядлый математик, поэтому он предложил вам подумать над такой задачей. Возможно ли так расположить детальки пазла, чтобы выполнялись следующие условия:

  • детальки расположены параллельно координатным осям;
  • детальки не накладываются друг на друга;
  • все детальки формируют единственную связную область (то есть от каждой детальки до каждой другой детальки существует путь по деталькам, в котором каждые две последовательные детальки имеют общую сторону);
  • отношение периметра этой области к площади этой области равно $$$\frac{p}{s}$$$;
  • количество использованных деталек не превышает $$$50\,000$$$.

Сможете ли вы справиться с ней?

У данной фигуры отношение периметра к площади равно $$$\frac{11}{9}$$$
Входные данные

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

Единственная строка каждого набора входных данных содержит два целых числа $$$p$$$ и $$$s$$$ ($$$1 \le p, s \le 50$$$).

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

Для каждого набора входных данных:

  • если невозможно расположить детальки вышеописанным образом, выведите одно целое число $$$-1$$$;
  • иначе в первой строке выведите одно целое число $$$k$$$ ($$$1 \le k \le 50\,000$$$), а далее в $$$k$$$ строках выведите координаты деталек: каждая строка должна содержать два целых числа $$$x_{i}$$$ и $$$y_{i}$$$ ($$$-10^{9} \le x_{i}, y_{i} \le 10^{9}$$$). Если подходящих вариантов расположения деталек несколько, выведите любой из них.
Примеры
Входные данные
2
1 1
31 4
Выходные данные
20
3 7
3 8
6 4
6 5
3 5
4 4
4 5
4 3
3 4
5 3
5 4
5 7
3 6
4 6
5 5
5 6
4 7
4 8
6 6
6 7
-1
Входные данные
2
4 2
12 5
Выходные данные
24
-7 2
-3 -3
-7 -5
-7 1
-3 2
-7 -2
-3 -5
-7 -6
-5 -6
-3 -4
-3 -6
-7 0
-6 -6
-7 -3
-5 2
-7 -1
-3 1
-4 -6
-3 0
-7 -4
-6 2
-4 2
-3 -1
-3 -2
5
0 0
0 1
1 0
-1 0
0 -1
Примечание

В первом наборе входных данных первого теста фигура может выглядеть так:

Во втором тесте фигуры выглядят так:

Обратите внимание, что внутренний периметр тоже учитывается!