#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int dp[18][125][2];
inline void solve(){
    ll n;cin>>n;
    vector<pair<int,int>> v;
    int x;for(int i:{0,1,2,3,4,5,6,7,8,9,1,5,10,50,100,500,1000})cin>>x,v.emplace_back(i,x);
    memset(dp,0x3f,sizeof dp);
    vector<int> d;while(n) d.push_back(n%10),n/=10;
    reverse(d.begin(),d.end());
    n=d.size();int inf=dp[0][0][0];
    dp[0][0][0]=0;
    for(int i=0;i<n;i++)
    for(int j=0;j<=120;j++)
    for(int k:{0,1})if(dp[i][j][k]<inf){
        int r=dp[i][j][k],w=j*10+d[i];
        for(auto [x,y]:v)if(x<=w&&w-x<=120){
            dp[i+1][w-x][k|!!x]=min(dp[i+1][w-x][k|!!x],r+(!k&&!x?0:y));
        }
    }
    cout<<dp[n][0][1]<<'\n';
}
int main(){
    std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--) solve();   
}