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