题目描述

有一个简单的问题是这个样子的。给定两个正整数$\red{n，m（m<=n）}$，对于一个 $\red{n}$阶 $\red{0-1}$矩阵，要求其任意$\red{m}$阶子矩阵中至少有一个元素$\red{0}$，求解这个矩阵中的$\red{1}$的最大数目。这个问题太简单了，请你解决这个问题的逆问题。

已知这个最大$\red{1}$的数目为$\red{x}$，求满足要求的 $\red{n}$ 和$\red{m}$的方案数。无解输出$\red{-1}$ 。

输入格式

每个测试点包含多组数据。

第一行一个整数$\red{T}$ 表示数据组数。

对于每组数据，一行一个整数 $\red{x}$如上所述。

输出格式

对于每组数据，输出一行，表示满足要求的方案数

样例

输入样例1

4

8

9

21

864477435

输出样例1

2

0

1

161

提示

1s, 1024KiB for each test case.

对于$\red{20\%}$的数据，$\red{ 0<x<=10}$

对于$\red{40\%}$的数据，$\red{0<x<=10,000}$

对于$\red{70\%}$的数据，$\red{0<x<=1,000,000}$

对于$\red{100\%}$的数据, $\red{1=<T<=1,000 ， 0<x<=10^9}$