Ran Yakumo симпатичная девочка, которая любит решать милые математические задачи.
Пусть \(f(x)\) будет минимальным квадратом строго большим, чем \(x\), и \(g(x)\) будет максимальным квадратом, не строго меньшим, чем \(x\). Например, \(f(1)=f(2)=g(4)=g(8)=4\).
Натуральное целое число \(x\) называется милым, если \(x-g(x)<f(x)-x\). Например, \(1,5,11\) это милые целые числа, а \(3,8,15\) нет.
Ran Yakumo дает вам массив \(a\) длины \(n\). Она хочет, чтобы вы нашли минимальное неотрицательное целое число \(k\), такое что \(a_i + k\) является милым числом для любого элемента массива \(a\).
Примечание
В первом тесте \(3\) не является красивым целым числом, поэтому \(k\ne 0\).
\(2,4,9,11\) являются милыми целыми числами, поэтому \(k=1\).