Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTIT015D - ACM PTIT 2015 D - Quà tặng

Tết thiếu nhi năm nay, ba bạn An, Bình, Cường lên kế hoạch làm các món quà tặng các bạn thiếu nhi ba miền Bắc, Trung, Nam. Các món quà được làm từ hai loại nguyên liệu: nguyên liệu loại A và nguyên liệu loại B. Nếu một món quà dùng x nguyên liệu loại A và y nguyên liệu loại B (x y là các số nguyên dương), thì thời gian làm món quà đó mất 2(x-1)3(y-1). Ba bạn dự định làm các món quà với tổng thời gian là n, giả sử a, b, c tương ứng là tổng giá trị các món quà cho ba miền Bắc, Trung, Nam thì a, b, c thỏa mãn các điều kiện sau:

1) a + b + c = n; 0 < a < b < c;

2) Với mỗi miền, các món quà tạo ra không thể so sánh được với nhau, có nghĩa là không tồn tại hai món quà có giá trị 2(x-1)3(y-1) và 2(u-1)3(v-1) mà đồng thời 0 < x u 0 < y ≤ v;

3) S(a) + S(b) + S(c) là lớn nhất, trong đó ký hiệu S(p) là tổng các chữ số của p.

Yêu cầu: Cho số nguyên dương n, hãy tìm cách tạo ra các món quà thỏa mãn điều kiện đề bài.

Input

Dữ liệu vào gồm nhiều bộ dữ liệu tương ứng với nhiều test. Dòng đầu tiên chứa số nguyên K (K≤100), là số bộ dữ liệu.

Tiếp theo là K dòng, mỗi dòng tương ứng với một bộ dữ liệu chứa một số nguyên dương n (n ≤ 1015).

Output

Với mỗi bộ dữ liệu, ghi ra trên một dòng câu trả lời, ghi một số nguyên là giá trị S(a) + S(b) + S(c)  lớn nhất tìm được.

Nếu bộ dữ liệu không tồn tại cách tạo ra các món quà thỏa mãn điều kiện đề bài thì trên dòng tương ứng chỉ ghi một số -1.

Example

Input:
2
9
21 Output: 9
21

Được gửi lên bởi:adm
Ngày:2015-04-19
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.