Условие
Задача H. Растер
---
Пешо е студент и изучава Компютърна графика. Днешната домашна работа е много лесна за него. Той трябва да напише програма, която изчертава права от точка (0, 0) до точка (a, b), в която целите числа a и b се въвеждат по време на изпълнение на програмата. Пешо прилага следния алгоритъм. Той разделя равнината на квадратчета 1x1, които представляват пиксели. Ако правата от точка (0, 0) до точка (a, b) пресича квадратче в повече от една точка, това квадратче (пиксел) трябва да бъде черно. В противен случай квадратчето е бяло, както е показано на фигурата.
Пешо направи домашното си за 30 минути и сега иска да реши малко по-различна задача. Ако е зададено цяло число N, с колко различни комплекта входни данни неговият алгоритъм ще получи точно N черни пиксела? Той се интересува само от прави, започващи в точка (0, 0) и завършващи в точка (a, b), където a и b са цели положителни числа. Напишете програма, която намира този брой.
Вход
---
Първият ред съдържа едно цяло число T – брой на тестовите примери. На следващите Т реда има по едно цяло положително число N.
Изход
---
За всеки тестов пример изведете едно цяло число – брой на правите, за изчертаването на които са нужни точно N черни пиксела.
Ограничения
---
a > 0, b > 0
1 ≤ N ≤ 1014
Примерен вход
---
2
2
6
Примерен изход
---
3
11
Обяснение на тестовия пример
---
Три прави могат да бъдат изчертани с помощта на два пиксела. Те завършват в точките (1,2), (2,1) и (2,2).
« Предходна страница
Решение
Въпрос