题目描述

奶牛王国现有货币系统的银币面值有 $1,2,5,10,20,50,100,200,500,1000,2000,5000,10000,20000,50000$。

现在农夫打算在现有货币系统的基础上，再推出一种新面值：newBanknote。

有 $N$ 头奶牛要购物，第 $i$ 头奶牛购买的商品的价值是 $cost[i]$。

现在你要回答 $N$ 个问题，第 $i$ 个问题是：至少需要多少枚银币才能恰好凑成 $cost[i]$ ？

输入格式

第一行，两个整数：$newBanknote$ 和 $N$ ( $1 \le newBanknote \le 2*10^9$ , $1 \le N \le 50$ )。

第二行，$N$ 个整数，第 $i$ 个整数是 $cost[i]$ ( $1 \le cost[i] \le 2*10^9$ )。

输出格式

共一行，$N$ 个整数，依次对应 $N$ 个问题的答案。

样例

4700 4
53 9400 9401 30000

3 2 3 2