题目描述

一个数被称为 2050 数 当且仅当这个数为 $2050 \cdot 10^k$（$k\geq 0$ 且 $k$ 为整数）。
给你一个正整数 $n$，请你将 $n$ 分成若干个不同的 2050 数的和（这些 2050 数 不一定是不同的）。请你计算 $n$ 最少能被分成多少个 2050 数 的和。如果不能，输出 -1.

输入格式

第一行一个正整数 $T$，表示有 $T$ 组测试数据。
接下来共 $T$ 行，每行一个正整数 $n$。

输出格式

对于每组测试数据，输出最少为多少个 2050 数 的和。如果无法被分成 2050 数 的和，请输出 -1

说明/提示

第 3 组测试数据，$4100 = 2050 + 2050$； 第 5 组测试数据，$22550 = 20500+2050$。

样例

6
205
2050
4100
20500
22550
25308639900

-1
1
2
1
2
36