题目描述

奶牛王国现有货币系统的银币面值有 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 <= newBanknote <= 2000000000 , 1<=N<=50 )。

第二行， N 个整数，第 i 个整数是 cost[i] ( 1 <= cost[i] <= 2000000000 )。

输出格式

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

样例

4700 4
53 9400 9401 30000

3 2 3 2