Покраска забора

У дяди Бори есть забор, состоящий из n досок. Дядя Боря хочет покрасить забор так, чтобы выполнялись следующие условия:

Каждая доска забора должна быть покрашена ровно в один из цветов — синий или зелёный. При этом хотя бы одна доска должна быть покрашена в синий цвет и хотя бы одна — в зелёный.
Покраска забора должна быть полосатой: для целых чисел a ≥ 1 и b ≥ 1 первые a досок должны быть покрашены в синий цвет, следующие b досок в зелёный цвет, следующие a досок опять в синий, и так далее. Последние a досок должны быть покрашены в синий цвет.
Все полосы шириной в a и b досок должны в точности покрывать весь забор. То есть, если синих полос получилось k штук, зелёных полос должно быть k-1 штук, и должно выполняться равенство ak + b(k-1) = n.
Помогите дяде Боре определить количество способов покраски забора, при которых выполняются все перечисленные выше условия. Две покраски забора считаются различными, если существует доска, покрашенная в синий цвет в одной покраске, а в другой — в зелёный.
Формат ввода
В первой строке входных данных дано целое число T — количество тестов (1 ≤ T ≤ 10).

В i-й из последующих T строк дано целое число n (1 ≤ n ≤ 1018).

Формат вывода
Выведите T целых чисел по одному в строке. i-е из них должно быть равно количеству способов покраски забора для i-го теста.

Пример
Ввод Вывод
5
1
5
7
12
20
0
3
5
6
14

0