#include <iostream> #include <cstdio> #include <math.h> #include <algorithm> #include <istream> #include <string> #include <queue> #include <deque> #include <random> #include <stack> #include <set> #include <string.h> #include <map> #include <unordered_map> #include <sstream> #include <bitset> #include <fstream> #include <climits> #include <time.h> #include <cassert> using namespace std; //#include "atcoder/all" // using namespace atcoder; //#pragma GCC optimize(3) //#pragma GCC optimize("Ofast") #define endl "\n" //#define int long long #define double long double #define pii pair<int, int> #define p1(x) (x).first #define p2(x) (x).second #define lc(x) ((x) << 1) #define rc(x) ((x) << 1 | 1) #define i128 __int128_t const int lim=50; int f[530][2*lim+1][2*lim+1]; string s; int n; int a[5010]; inline void chkmn(int &x,int y){ x=min(x,y); } inline void slv(){ cin>>s; n=s.size(); a[n]=0; for(int i=0;i<n;i++) a[n-i-1]=s[i]-'0'; // n++; a[n+1]=0; if(n<=500){ int lim=min(n+10,50); n++; for(int i=0;i<=n;i++) for(int p=-lim;p<=lim;p++) for(int q=-lim;q<=lim;q++) f[i][p+lim][q+lim]=1e9; f[n][lim][lim]=0; for(int i=n;i>=1;i--) for(int p=-lim;p<=lim;p++) for(int q=-lim;q<=lim;q++){ int x=f[i][p+lim][q+lim]; for(int s=-lim;s<=lim;s++){ int rem=p+s; int nxt=q*10+rem-a[i-1]; if(abs(rem)>lim||abs(nxt)>lim)continue; chkmn(f[i-1][rem+lim][nxt+lim],x+abs(s)*i); } } int res=1e9; for(int i=-lim;i<=lim;i++) for(int j=-lim;j<=lim;j++) chkmn(res,f[0][i+lim][lim]); cout<<res<<endl; } else{ int res=0; for(int i=n-1;i>=0;i--) res+=abs(a[i]-a[i+1])*i; cout<<res<<endl; } } inline void MT(){ int t; cin>>t; while(t--)slv(); } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // freopen("/Users/noip2019/Desktop/liuyile/ones/ones.in","r",stdin); // freopen("ones.in","r",stdin); // freopen("ones.out","w",stdout); MT(); // slv(); cout.flush(); return 0; } /* 13 0 1 0 0 0 0 1 0 1 1 0 1 0 */