题目描述

一个数是 $2050$ 数，当且仅当它是 $2050,20500,\dots,2050\times 10^k(k\ge 0)$

本题需要你回答 $T$ 组独立的如下问题：

给一个正整数 $n$，你需要判断它是否为若干个 $2050$ 数的和，如果是，输出它最小可以由多少个 $2050$ 数相加构成，否则输出 $-1$.

输入格式

第一行一个整数 $T$， 表示数据组数。

接下来 $T$ 行，每行一个整数表示 $n$。

输出格式

共 $T$ 行，第 $i$ 行输出一个整数表示第 $i$ 组询问的答案。

样例

Input # 1

6
205
2050
4100
20500
22550
25308639900

Output # 1

-1
1
2
1
2
36

数据范围与提示

对于 $10\%$ 的数据，有 $n\le 10^5$

对于 $30\%$ 的数据，有 $n\le 10^8$

对于 $100\%$ 的数据，有 $1\le T\le 10^3,1\le n\le 10^{18}$