题目描述

有一个简单的问题是这个样子的。

给定两个正整数 $\red{n,m(m≤}$$\red{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}$如上所述。

样例

输入样例

4

8

9

21

864477435

输出样例

2

0

1

161

提示

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

对于 $\red{40\% }$的数据，$\red{0<x≤}$ $\red{10^4}$。

对于 $\red{70\% }$的数据，$\red{0<x≤}$$\red{10^6}$。

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