В приведенной ниже формуле следует расставить знаки '+' и '-' вместо '?' так, чтобы получить число 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 по выше приведенной формуле.