Фигуры с простым смыслом
Думаете, что рисовать многоугольники легко? Это не тот случай, если у Вас имеются некоторые ограничения.
В этой задаче от Вас требуется нарисовать многоугольник. Он должен иметь в точности n вершин. Он не должен содержать самопересечений. Никакие три последовательные вершины не должны быть коллинеарными. Все координаты вершин должны быть целыми числами в пределах от 0 до 10 000 включительно. Просто, не так ли?
Однако имеется одно ограничение. Количество внутренних углов многоугольника, равных 90°, должно быть максимально возможным. Что Вы об этом думаете?
Входные данные
Сначала идет сообщение о количестве тестов t (1 ≤ t ≤ 30), за которым следуют t целых чисел n (3 ≤ n ≤ 1000).
Выходные данные
Для каждого теста вывести наибольшее количество внутренних углов, равных 90°, за которым следует n пар целых чисел - координаты вершин многоугольника, перечисленные по часовой или против часовой стрелки. Если существует несколько решений, то вывести любое.