Một số \(X\) được gọi là số khối lập phương nếu \(X\) là lũy thừa bậc \(3\) của số \(Y\) (\(X = Y^{3}\)). Cho số nguyên dương \(N\), nhiệm vụ của bạn là tìm số khối lập phương lớn nhất bằng cách loại bỏ đi các chữ số của \(N\). Ví dụ, với số \(4125\), ta có kết quả là \(125 = 5^{3}\).

Input

• Dòng đầu tiên đưa vào số lượng bộ test \(T\) (\(1 \leq T \leq 100\)).
• Những dòng kế tiếp đưa vào các bộ test. Mỗi bộ test là một số tự nhiên \(N\) (\(1 \leq N \leq 10^{18}\)) được viết trên một dòng.

Output

• Đưa ra kết quả mỗi test theo từng dòng. Nếu không tìm được đáp án, in ra \(-1\).

Example

2
4125
976

125
-1