題目連結：
題目大意：
第一列給定一正整數 Ｔ （ １ ≦ Ｔ ≦ １, ０００, ００１ ），代表接下來有Ｔ列的輸入。
每一列的輸入包含一正整數 Ｎ （ ０ ≦ Ｎ ≦ ２, ０００, ０００, ０００ ），代表要帶 Ｎ 塊錢。
而現在有 １、５、１０、３０、５０、７０、１００、１１０、５００、１０００ 塊面額的硬幣，求要湊到 Ｎ 塊錢所需的最少硬幣數量為何？
範例輸入：
3
30
140
250
範例輸出：
1
2
3
解題思維：
乍看之下像是一題非常一般的ＤＰ題。但是由於Ｎ實在太大，建表不實際，而輸入時才求解也是不大明智的選擇。
因此我們可以想辦法降低需要求解的範圍。經過一番思考，我們可以發現當 Ｎ ≧ １０００ ，最佳的方法數必定為：
Floor（Ｎ / １０００）＋（ Ｎ mod １０００ ）之方法數。
其中，Floor（）代表將結果取下高斯（對正數來說，無條件捨去；負數則為無條件進位）。因為如果不用 １０００ 塊的話，想要快速逼近 Ｎ 塊錢就必須要至少兩個 ５００ 塊，但是兩個 ５００ 塊可以替換成一個 １０００ 塊，因而造成上式的結果。
相似地，我們也可以求出當 ５００ ≦ Ｎ ＜ １０００ 時，方法數為：
Floor（Ｎ / ５００）＋（ Ｎ mod ５００ ）之方法數。
其中的理由跟上面相同。
經過以上篩選後，真正需要算的範圍也只剩下 Ｎ ＜ ５００ 以下了，此時就可以套用之前的文章提到過的方法去ＤＰ。最後只要每輸入一次 Ｎ 就進行以上的關係式，再加上取完餘數（值必定介於 ０ ～ ４９９ 之間）相應的方法數即可。
