У наведеній нижче формулі слід розташувати знаки '+' та '-' замість '?' так, щоб отримати число k:

? 1 ? 2 ? ... ? n = k

Наприклад, для отримання k = 12 вираз прийме вигляд:

- 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12, де n = 7.

Вхідні дані

Перший рядок містить кількість тестів. Кожен тест містить одне ціле число k (0 ≤ |k| ≤ 109).

Вихідні дані

Для кожного тесту в окремому рядку вивести найменше можливе n (1 ≤ n), для якого можна отримати k за вище наведеною формулою.