#include <stdio.h>
#include <string.h>

#define ok(a,b) (b!=4 && !(a==1 && b==3))

long long dp[10][13], T, h;
char k[100];

int main(){
    for (int F=0; F<10; F++) dp[F][0] = 1;
    for (int L=1; L<13; L++)
        for (int F=0; F<10; F++) if (F!=4) 
            for (int D=0; D<10; D++) if (ok(F,D))
                dp[F][L] += dp[D][L-1];

    scanf("%lld",&T);
    while (T--){
        scanf("%s %lld",k,&h);
        long long floors = 0;
        for (int i=0, L=strlen(k); i<L; i++)
            for (int F=0; F<k[i]-'0'; F++)
                if (ok(i==0?0:k[i-1]-'0',F))
                    floors += dp[F][L-i-1];
        printf("%lld\n",floors * h);
    }
}

#include <stdio.h>
#include <string.h>

long long dp[13][2], x, h, res;
int num[13], len, T;

long long rec(int len, int prev1){
    if (len==0) return 1;
    long long &ret = dp[len][prev1];
    if (ret!=-1) return ret; else ret = 0;
    for (int i=0; i<10; i++)
        if (i!=4 && !(prev1 && i==3))
            ret += rec(len-1, i==1);
    return ret;
}

int main(){
    memset(dp,-1,sizeof(dp));
    for (scanf("%d",&T); T; T--){
        scanf("%lld %lld",&x,&h);
        for (len=0; x; x/=10) num[len++] = x%10;
        for (int i=res=0; i<len; i++)
            for (int F=0; F<num[len-i-1]; F++)
                if (F!=4 && (i==0 || num[len-i]!=1 || F!=3))
                    res += rec(len-i-1, F==1);
        printf("%lld\n",res*h);
    }
}

import java.util.*;

public class Super {
    public static void main(String[] args){
        long[][] dp = new long[10][13];
        for (int F=0; F<10; F++) dp[F][0] = 1;
        for (int L=1; L<13; L++)
            for (int F=0; F<10; F++) if (F!=4) 
                for (int D=0; D<10; D++)
                    if (D!=4 && !(F==1 && D==3))
                        dp[F][L] += dp[D][L-1];

        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();
        while (T-- > 0){
            char[] k = scan.next().toCharArray();
            long floors = 0;
            for (int i=0; i<k.length; i++)
                for (int F=0; F < k[i]-'0'; F++)
                    if (F!=4 && !(i>0 && k[i-1]=='1' && F==3))
                        floors += dp[F][k.length-i-1];
            System.out.println(floors * scan.nextInt());
        }
    }
}

import java.util.*;

public class SuperDPTopDown {
    long[][] memo = new long[10][13];

    long rec(int first, int length){
        if (length==0) return 1;
        if (memo[first][length]!=-1)
            return memo[first][length];

        long ret = 0;
        for (int i=0; i<10; i++)
            if (i!=4 && !(first==1 && i==3))
                ret += rec(i,length-1);
        return memo[first][length] = ret;
    }

    long countFloors(char[] k){
        long floors = 0;
        for (int i=0; i<k.length; i++)
            for (int j=0; j<k[i]-'0'; j++)
                if (j!=4 && !((i>0?k[i-1]-'0':0)==1 && j==3))
                    floors += rec(j,k.length-i-1);
        return floors;
    }

    void solve(){
        for (long[] m : memo) Arrays.fill(m,-1);
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();
        while (T-- > 0){
            long floors = countFloors(scan.next().toCharArray());
            System.out.println(floors * scan.nextInt());
        }
        scan.close();
    }

    public static void main(String[] args){
        new SuperDPTopDown().solve();
    }
}

#include <stdio.h>
#include <string.h>

#define MAXN 18

int T,C,F,N,cost[MAXN],conf[MAXN],depend[MAXN];
int memo[1<<MAXN], inf = 100000000;

int rec(int def){
    if (def==(1<<N)-1) return 0;
    int &ret = memo[def];
    if (ret!=-1) return ret; else ret = inf;
    for (int i=0; i<N; i++) if ((def&(1<<i))==0){
        if ((depend[i] & def) != depend[i]) continue;

        int lines = 0;
        for (int j=0; j<N && conf[j]!=i; j++)
            if ((def&(1<<conf[j]))==0) lines += cost[conf[j]];
        int ccost = lines * cost[i] + rec(def | (1<<i));
        if (ccost < ret) ret = ccost;
    }
    return ret;
}

int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%d",&N);
        for (int i=0; i<N; i++)
            scanf("%d",&cost[i]);

        memset(depend,0,sizeof(depend));
        for (int i=0; i<N; i++)
            for (scanf("%d",&C); C--; ){
                scanf("%d",&F);
                if (i!=F-1) depend[i] |= 1<<(F-1);
            }

        for (int i=0; i<N; i++)
            scanf("%d",&conf[i]), conf[i]--;

        memset(memo,-1,sizeof(memo));
        int res = rec(0);
        printf("%d\n",res==inf? -1 : res);
    }
}

#include <stdio.h>
#include <string.h>

#define MAXN 18

int T,C,F,N,cost[MAXN],conf[MAXN],depend[MAXN];
int memo[1<<MAXN],lines[1<<MAXN], inf = 100000000;

int rec(int def){
    if (def==(1<<N)-1) return 0;
    int &ret = memo[def];
    if (ret!=-1) return ret; else ret = inf;
    for (int i=0; i<N; i++) if ((def&(1<<i))==0){
        if ((depend[i] & def) != depend[i]) continue;
        int moved = lines[(((1<<N)-1)^def) & ((1<<i)-1)];
        int ccost = moved*cost[i] + rec(def|(1<<i));
        if (ccost < ret) ret = ccost;
    }
    return ret;
}

int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%d",&N);
        for (int i=0; i<N; i++)
            scanf("%d",&cost[i]);

        memset(depend,0,sizeof(depend));
        for (int i=0; i<N; i++)
            for (scanf("%d",&C); C--; ){
                scanf("%d",&F);
                if (i!=F-1) depend[i] |= 1<<(F-1);
            }

        for (int i=0; i<N; i++)
            scanf("%d",&conf[i]), conf[i]--;

        for (int i=0; i<(1<<N); i++){
            int mask = 0, sum = 0;
            for (int j=0; j<N; j++)
                if ((i&(1<<j))!=0){
                    sum += cost[conf[j]];
                    mask |= 1<<conf[j];
                }
            lines[mask] = sum;
        }

        memset(memo,-1,sizeof(memo));
        int res = rec(0);
        printf("%d\n",res==inf? -1 : res);
    }
}

import java.util.*;

public class Panda {
    int[] memo = new int[1<<18];
    int[] cost, conf, depend;
    int N, inf = 100000000;

    int rec(int idx, int def){
        if (idx==N) return 0;
        if (memo[def]!=-1) return memo[def];

        int ret = inf;
        for (int i=0; i<N; i++) if ((def&(1<<i))==0){
            if ((depend[i] & def) != depend[i]) continue;

            int lines = 0;
            for (int j=0; j<N && conf[j]!=i; j++)
                if ((def&(1<<conf[j]))==0) lines += cost[conf[j]];
            ret = Math.min(ret, lines*cost[i]+rec(idx+1,def|(1<<i)));
        }
        return memo[def] = ret;
    }

    void solve(){
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();
        while (T-- > 0){
            N = scan.nextInt();
            cost = new int[N];
            for (int i=0; i<N; i++) cost[i] = scan.nextInt();
            depend = new int[N];
            for (int i=0; i<N; i++)
                for (int C = scan.nextInt(); C-- > 0;){
                    int F = scan.nextInt() - 1;
                    if (i!=F) depend[i] |= 1 << F;
                }
            conf = new int[N];
            for (int i=0; i<N; i++) conf[i] = scan.nextInt()-1;
            Arrays.fill(memo,-1);
            System.out.printf("%d\n",rec(0,0)==inf?-1:rec(0,0));
        }
    }

    public static void main(String[] args){
        new Panda().solve();
    }
}

#include <stdio.h>
#include <string.h>

#define MAXN 18

int T,C,F,n,cost[MAXN],conf[MAXN];
int lines[1<<MAXN][MAXN];
int dp[MAXN+1][1<<MAXN];
int depend[MAXN];
int inf = 100000000;

int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%d",&n);
        for (int i=0; i<n; i++)
            scanf("%d",&cost[i]);

        memset(depend,0,sizeof(depend));
        for (int i=0; i<n; i++)
            for (scanf("%d",&C); C--; ){
                scanf("%d",&F);
                if (i!=F-1) depend[i] |= 1<<(F-1);
            }

        for (int i=0; i<n; i++)
            scanf("%d",&conf[i]), conf[i]--;

        memset(dp[0], 0, sizeof(dp[0]));
        for (int i=1; i<=n; i++)
            for (int j=0; j<(1<<n); j++)
                dp[i][j] = inf;

        memset(lines,0,sizeof(lines));
        for (int def=0; def<(1<<n); def++)
            for (int i=0; i<n; i++) if ((def&(1<<i))==0)
                for (int j=0; j<n && conf[j]!=i; j++)
                    if ((def&(1<<conf[j]))==0) lines[def][i] += cost[conf[j]];

        for (int idx=0; idx<n; idx++){
            for (int def=0; def<(1<<n); def++) if (dp[idx][def]<inf) {
                for (int i=0; i<n; i++) if ((def&(1<<i))==0 && (depend[i]&def)==depend[i]){
                    int cur = lines[def][i] * cost[i] + dp[idx][def];
                    int &next = dp[idx+1][def|(1<<i)];
                    if (cur < next) next = cur;
                }
            }
        }
                
        int res = dp[n][(1<<n)-1];
        printf("%d\n",res==inf? -1 : res);
    }
}

import java.util.*;

public class PandaBTU {
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        for (int T = scan.nextInt(); T > 0; T--){
            int N = scan.nextInt();
            int[] cost = new int[N];
            for (int i=0; i<N; i++)
                cost[i] = scan.nextInt();

            int[] depend = new int[N];
            for (int i=0; i<N; i++)
                for (int C = scan.nextInt(); C-- > 0;){
                    int F = scan.nextInt() - 1;
                    if (i!=F) depend[i] |= 1 << F;
                }

            int[] conf = new int[N];
            for (int i=0; i<N; i++)
                conf[i] = scan.nextInt()-1;

            int[] lines = new int[1<<N];
            for (int i=0; i<(1<<N); i++){
                int mask = 0, sum = 0;
                for (int j=0; j<N; j++)
                    if ((i&(1<<j))!=0){
                        sum += cost[conf[j]];
                        mask |= 1<<conf[j];
                    }
                lines[mask] = sum;
            }

            Integer[] hamming = new Integer[1<<N];
            for (int i=0; i<(1<<N); i++) hamming[i] = i;
            Arrays.sort(hamming, new Comparator<Integer>(){
                public int compare(Integer a, Integer b){
                    return Integer.bitCount(a) - Integer.bitCount(b);
                }
            });

            int[] dp = new int[1<<N];
            int inf = 1000000000;
            Arrays.fill(dp, inf);
            dp[0] = 0;
            for (int def : hamming){
                for (int i=0; i<N; i++) if ((def&(1<<i))==0){
                    if ((depend[i] & def) != depend[i]) continue;
                    int moved = lines[(((1<<N)-1)^def) & ((1<<i)-1)];
                    int ccost = dp[def] + moved*cost[i];
                    dp[def|(1<<i)] = Math.min(dp[def|(1<<i)], ccost);
                }
            }
            int res = dp[(1<<N)-1];
            System.out.printf("%d\n",res==inf?-1:res);
        }
    }
}

#include <stdio.h>

struct Point { long long x,y; };
Point A[1000], B[1000], X;
int nA, nB, T, aL, aR, bL, bR;

// return true jika a-b-c belok kiri, false jika bukan
#define left(a,b,c) ((a.x*b.y + b.x*c.y + c.x*a.y - a.y*b.x - b.y*c.x - c.y*a.x) > 0)

int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%d",&nA); for (int i=0; i<nA; i++) scanf("%d %d",&A[i].x,&A[i].y);
        scanf("%d",&nB); for (int i=0; i<nB; i++) scanf("%d %d",&B[i].x,&B[i].y);
        scanf("%d %d",&X.x,&X.y);

        aL = aR = bL = bR = 0;     // pilih titik 0 sebagai titik paling kiri/kanan
        for (int i=0; i<nA; i++){
            if (left(X,A[aL],A[i])) aL = i;  // update titik paling kiri polygon A
            if (!left(X,A[aR],A[i])) aR = i; // update titik paling kanan polygon A
        }
        for (int i=0; i<nB; i++){
            if (left(X,B[bL],B[i])) bL = i;  // update titik paling kiri polygon B
            if (!left(X,B[bR],B[i])) bR = i; // update titik paling kanan polygon B
        }

        Point P=A[aL], Q=A[aR], R=B[bL], S=B[bR]; // P,Q,R,S didefinisikan diatas

        bool gray = !left(X,R,P) && left(X,S,Q) && left(R,S,P) && left(R,S,Q);
        bool cyan = left(X,R,Q) || !left(X,S,P);
        bool kuning = !left(R,S,P) && !left(R,S,Q);

        if (gray){
            puts("NO VISION");
        } else if (cyan || kuning){
            puts("CLEAR");
        } else {
            puts("ALMOST CLEAR");
        }
    }
}

import java.util.*;

public class Poly {
    class Point { long x,y; }

    // return true jika a-b-c belok kiri, false jika bukan
    boolean left(Point a, Point b, Point c){
        return (a.x*b.y + b.x*c.y + c.x*a.y - a.y*b.x - b.y*c.x - c.y*a.x) > 0;
    }

    void solve(){
        Scanner scan = new Scanner(System.in);
        for (int T = scan.nextInt(); T > 0; T--){
            Point[] A = new Point[scan.nextInt()];
            for (int i=0; i<A.length; i++){
                A[i] = new Point();
                A[i].x = scan.nextInt();
                A[i].y = scan.nextInt();
            }
            Point[] B = new Point[scan.nextInt()];
            for (int i=0; i<B.length; i++){
                B[i] = new Point();
                B[i].x = scan.nextInt();
                B[i].y = scan.nextInt();
            }
            Point X = new Point();
            X.x = scan.nextInt();
            X.y = scan.nextInt();

            int aL=0,aR=0,bL=0,bR=0;   // pilih titik 0 sebagai titik paling kiri/kanan
            for (int i=0; i<A.length; i++){
                if (left(X,A[aL],A[i])) aL = i;  // update titik paling kiri polygon A
                if (!left(X,A[aR],A[i])) aR = i; // update titik paling kanan polygon A
            }
            for (int i=0; i<B.length; i++){
                if (left(X,B[bL],B[i])) bL = i;  // update titik paling kiri polygon B
                if (!left(X,B[bR],B[i])) bR = i; // update titik paling kanan polygon B
            }

            Point P=A[aL], Q=A[aR], R=B[bL], S=B[bR]; // P,Q,R,S didefinisikan diatas

            boolean gray = !left(X,R,P) && left(X,S,Q) && left(R,S,P) && left(R,S,Q);
            boolean cyan = left(X,R,Q) || !left(X,S,P);
            boolean kuning = !left(R,S,P) && !left(R,S,Q);

            if (gray){
                System.out.println("NO VISION");
            } else if (cyan || kuning){
                System.out.println("CLEAR");
            } else {
                System.out.println("ALMOST CLEAR");
            }
        }
    }

    public static void main(String[] args){
        new Poly().solve();
    }
}

#include <stdio.h>
#include <stdlib.h>

int intcmp(const void *a, const void *b){
    return *(int*)a - *(int*)b;
}

int T,N,M,A[20000],B[20000];

int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%d %d",&N,&M);
        for (int i=0; i<N; i++) scanf("%d",&A[i]);
        for (int i=0; i<M; i++) scanf("%d",&B[i]);
        qsort(A,N,sizeof(int),intcmp);
        qsort(B,M,sizeof(int),intcmp);

        int total = 0;
        while (N>0 && M>0){
            if (A[N-1] > B[M-1])
                total += M, N--;
            else
                M--;
        }
        printf("%d\n",total);
    }
}

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int T,N,M;

int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%d %d",&N,&M);
        vector<int> A(N), B(M);
        for (int i=0; i<N; i++) scanf("%d",&A[i]);
        for (int i=0; i<M; i++) scanf("%d",&B[i]);
        sort(A.begin(),A.end());
        sort(B.begin(),B.end());

        int total = 0;
        while (N>0 && M>0){
            if (A[N-1] > B[M-1])
                total += M, N--;
            else
                M--;
        }
        printf("%d\n",total);
    }
}

import java.util.*;

public class Eat {
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        for (int T = scan.nextInt(), N, M; T-- > 0; ){
            int[] A = new int[N = scan.nextInt()];
            int[] B = new int[M = scan.nextInt()];
            for (int i=0; i<N; i++) A[i] = scan.nextInt();
            for (int i=0; i<M; i++) B[i] = scan.nextInt();
            Arrays.sort(A);
            Arrays.sort(B);

            int total = 0;
            while (N>0 && M>0){
                if (A[N-1] > B[M-1]){
                    total += M;
                    N--;
                } else {
                    M--;
                }
            }
            System.out.println(total);
        }
    }
}

#include <stdio.h>
#include <math.h>

// returns nCk(N,S) * 2^(N-S)
double calc(int N, int S){
    double nCk = 1.0;
    for (int i=1; i<=S; i++) nCk *= (N-i+1.0) / i;
    return nCk * pow(2.0,N-S);
}

int main(){
    for (int N,S; scanf("%d %d",&N,&S)!=EOF; ){
        if (S>N){
            puts("100.00000");
        } else {
            double total = 0, gak_dapet = calc(N,S);
            for (int i=0; i<=S; i++) total += calc(N,i);
            double dapet = total - gak_dapet;
            printf("%.5lf\n",100.0*dapet/total);
        }
    }
}

#include <cstdio>
#include <cmath>
using namespace std;

int main(){
    int n, s;
    while ( scanf( "%d %d", &n, &s ) == 2 ) {
        double x = pow(2.0, n - s);
        for ( int i = 1; i <= s; i++ )
            x *= (double)(n - i + 1)/i;

        double b = pow(2.0, n), v = 1, w = 1;
        for ( int i = 1; i <= s; i++ ) {
            v *= n - i + 1; w *= i;
            b += pow(2.0, n - i) * v / w;
        }
        printf( "%.5lf\n", (b - x) * 100.0 / b );
    }
    return 0;
}

#include <stdio.h>

int main(){
    double dp[52][52];

    for (int i=0; i<52; i++) dp[0][i] = 1.0;
    
    for (int i=1; i<52; i++)
        for (int j=0; j<52; j++)
            dp[i][j] = 2*dp[i-1][j] + (j>0?dp[i-1][j-1]:0);

    for (int N, S; scanf("%d %d",&N,&S)!=EOF; )
        printf("%.5f\n",100.0*dp[N][S-1]/dp[N][S]);
}

#include <stdio.h>
#include <string.h>

double dp[52][52];
char vis[52][52];

double rec(int N, int S){
    if (N<0 || S<0) return 0;
    if (N==0) return 1;
    if (vis[N][S]) return dp[N][S]; else vis[N][S] = 1;
    return dp[N][S] = 2*rec(N-1,S) + rec(N-1,S-1);
}

int main(){
    for (int N,S; scanf("%d %d",&N,&S)!=EOF; ){
        memset(vis,0,sizeof(vis));
        printf("%.5lf\n", 100.0 * rec(N,S-1) / rec(N,S));
    }
}

import java.util.*;

public class Indomie {
    public static void main(String[] args){
        double[][] dp = new double[52][52];
        for (int i=1; i<52; i++) dp[0][i] = 1.0;
        for (int i=1; i<52; i++)
            for (int j=1; j<52; j++)
                dp[i][j] = 2*dp[i-1][j] + dp[i-1][j-1];

        // dp[i][j] digeser menjadi dp[i][j+1]
        Scanner scan = new Scanner(System.in);
        while (scan.hasNextInt()){
            int N = scan.nextInt(), S = scan.nextInt();
            System.out.printf("%.5f\n",100.0*dp[N][S]/dp[N][S+1]);
        }
    }
}

#include <stdio.h>
#include <string.h>

#define MAXV 10000
#define MAXR 101000
#define MAXC 5

char op[10], rem[MAXR];
int col[MAXC][MAXV+1];
int data[MAXR][MAXC];
int T,a,b,x,m,n;

int main(){
    scanf("%d",&T);
    for (int TC=1; TC<=T; TC++){
        printf("Case #%d:\n",TC);
        scanf("%d %d %d %d %d",&a,&b,&x,&m,&n);
        memset(data,0,sizeof(data));
        memset(rem,0,sizeof(rem));
        memset(col,0,sizeof(col));
        for (int r=0; r<n; r++)
            for (int c=0; c<MAXC; c++){
                long long v1 = (long long) a * (r==0?0:data[r-1][c]);
                long long v2 = (long long) b * (c==0?0:data[r][c-1]);
                data[r][c] = (v1 + v2 + x) % m;
                col[c][data[r][c]]++;
            }

        int q,r,c;
        scanf("%d",&q);
        while (q-- > 0){
            scanf("%s",op);
            if (op[0]=='i'){
                for (c=0; c<MAXC; c++){
                    scanf("%d",&data[n][c]);
                    col[c][data[n][c]]++;
                }
                n++;
            } else if (op[1]=='e'){
                scanf("%d",&r); r--;
                if (r<0 || r>=n || rem[r]) continue;
                for (c=0; c<MAXC; c++) col[c][data[r][c]]--;
                rem[r] = 1;
            } else if (op[2]=='x'){
                scanf("%d",&c); c--;
                for (int v=MAXV; v>=0; v--)
                    if (col[c][v]){ printf("%d\n",v); break; }
            } else if (op[1]=='i'){
                scanf("%d",&c); c--;
                for (int v=0; v<=MAXV; v++)
                    if (col[c][v]){ printf("%d\n",v); break; }
            } else {
                scanf("%d %d %d",&c,&a,&b); c--;
                int cnt = 0;
                for (int v=a; v<=b; v++) cnt += col[c][v];
                printf("%d\n",cnt);
            }
        }
    }
}

import java.util.*;

public class Query {
    public static void main(String[] args){
        final int MAXV = 10000, MAXR = 100100, MAXC = 5;
        boolean[] rem = new boolean[MAXR];
        int[][] col = new int[MAXC][MAXV+1];
        int[][] arr = new int[MAXR][MAXC];

        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();
        for (int TC=1; TC<=T; TC++){
            System.out.printf("Case #%d:\n",TC);

            int a = scan.nextInt();
            int b = scan.nextInt();
            int x = scan.nextInt();
            int m = scan.nextInt();
            int n = scan.nextInt();
            Arrays.fill(rem,false);
            for (int[] c : col) Arrays.fill(c,0);

            for (int r=0; r<n; r++)
                for (int c=0; c<MAXC; c++){
                    long v1 = (long) a * (r==0?0:arr[r-1][c]);
                    long v2 = (long) b * (c==0?0:arr[r][c-1]);
                    arr[r][c] = (int) ((v1 + v2 + x) % m);
                    col[c][arr[r][c]]++;
                }

            int q = scan.nextInt();
            while (q-- > 0){
                String op = scan.next();
                if (op.charAt(0)=='i'){
                    for (int c=0; c<MAXC; c++){
                        arr[n][c] = scan.nextInt();
                        col[c][arr[n][c]]++;
                    }
                    n++;
                } else if (op.charAt(1)=='e'){
                    int r = scan.nextInt() - 1;
                    if (r<0 || r>=n || rem[r]) continue;
                    for (int c=0; c<MAXC; c++) col[c][arr[r][c]]--;
                    rem[r] = true;
                } else if (op.charAt(2)=='x'){
                    int c = scan.nextInt() - 1;
                    for (int v=MAXV; v>=0; v--) if (col[c][v]>0){
                        System.out.printf("%d\n",v); break; }
                } else if (op.charAt(1)=='i'){
                    int c = scan.nextInt() - 1;
                    for (int v=0; v<=MAXV; v++) if (col[c][v]>0){
                        System.out.printf("%d\n",v); break; }
                } else {
                    int c = scan.nextInt() - 1;
                    int L = scan.nextInt();
                    int R = scan.nextInt();
                    int cnt = 0;
                    for (int v=L; v<=R; v++) cnt += col[c][v];
                    System.out.printf("%d\n",cnt);
                }
            }
        }
    }
}

#include <stdio.h>

struct Hotel {
    int bedSize, roomCapacity, nAvailable, roomPrice;
    char name[30];
};

Hotel hs[51];
int T, nH, nT;

int main(){
    scanf("%d",&T);
    for (int TC=1; TC<=T; TC++){
        printf("Case #%d:\n",TC);
        scanf("%d %d",&nH,&nT);
        
        for (int i=0; i<nH; i++){
            scanf("%d",&hs[i].bedSize);
            scanf("%d",&hs[i].roomCapacity);
            scanf("%d",&hs[i].nAvailable);
            scanf("%d",&hs[i].roomPrice);
            scanf("%s",hs[i].name);
        }

        for (int i=0; i<nT; i++){
            char type[10];
            int nPeople, maxPerson;
            scanf("%s %d %d",type,&nPeople,&maxPerson);

            int totalCost = 1000000000, bedSize, suggestedHotel = -1;
            for (int j=0; j<nH; j++){
                int nPersonPerRoom = hs[j].roomCapacity;
                if (nPersonPerRoom > maxPerson) nPersonPerRoom = maxPerson;
                int nRoom = (nPeople + nPersonPerRoom - 1) / nPersonPerRoom;
                if (nRoom > hs[j].nAvailable) continue;

                int range[] = { 0, 35, 48, 62 };
                int idx = type[0]-'A';
                int min = range[idx] + 1;
                int max = range[idx + 1];
                if (hs[j].bedSize < min || max < hs[j].bedSize) continue;

                int price = nRoom * hs[j].roomPrice;
                if (price > totalCost) continue;
                if (price == totalCost && hs[j].bedSize <= bedSize) continue;

                totalCost = price;
                bedSize = hs[j].bedSize;
                suggestedHotel = j;
            }
            
            if (suggestedHotel != -1)
                printf("%d %s\n",totalCost,hs[suggestedHotel].name);
            else
                puts("no-hotel");
        }
    }
}

import java.util.*;

public class Hotel {
    int bedSize, roomCapacity, nAvailable, roomPrice;
    String name;

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();
        for (int TC=1; TC<=T; TC++){
            System.out.printf("Case #%d:\n",TC);

            int nH = scan.nextInt();
            int nT = scan.nextInt();
            
            Hotel[] hs = new Hotel[nH];
            for (int i=0; i<nH; i++){
                hs[i] = new Hotel();
                hs[i].bedSize = scan.nextInt();
                hs[i].roomCapacity = scan.nextInt();
                hs[i].nAvailable = scan.nextInt();
                hs[i].roomPrice = scan.nextInt();
                hs[i].name = scan.next();
            }

            for (int i=0; i<nT; i++){
                String type = scan.next();
                int nPeople = scan.nextInt();
                int maxPerson = scan.nextInt();

                String suggestedHotel = "no-hotel";
                int totalCost = Integer.MAX_VALUE;
                int bedSize = Integer.MIN_VALUE;
                for (int j=0; j<nH; j++){
                    int nPersonPerRoom = Math.min(maxPerson, hs[j].roomCapacity);
                    int nRoom = (nPeople + nPersonPerRoom - 1) / nPersonPerRoom;
                    if (nRoom > hs[j].nAvailable) continue;

                    int[] range = new int[]{ 0, 35, 48, 62 };
                    int idx = type.charAt(0)-'A';
                    int min = range[idx] + 1;
                    int max = range[idx + 1];
                    if (hs[j].bedSize < min || max < hs[j].bedSize) continue;

                    int price = nRoom * hs[j].roomPrice;
                    if (price > totalCost) continue;
                    if (price == totalCost && hs[j].bedSize <= bedSize) continue;

                    totalCost = price;
                    bedSize = hs[j].bedSize;
                    suggestedHotel = hs[j].name;
                }
                
                if (totalCost < Integer.MAX_VALUE)
                    System.out.printf("%d ",totalCost);
                System.out.println(suggestedHotel);
            }
        }
    }
}

#include <stdio.h>
#include <string.h>
#include <string>

using namespace std;

char s[100];
long long N;
int L;

string wal(int L, long long N){
    if (L==1) return string(1,(char)('0'+N));
    long long H = 1LL << (L-1);
    switch ((L-2)%8){
        case 0: return (N<H)? (wal(L-1,N)+"0") : (wal(L-1,N-H)+"1");
        case 1: return (N<H)? ("0"+wal(L-1,N)) : ("1"+wal(L-1,N-H));
        case 2: return (N<H)? (wal(L-1,N)+"1") : (wal(L-1,N-H)+"0");
        case 3: return (N<H)? ("1"+wal(L-1,N)) : ("0"+wal(L-1,N-H));
        case 4: return (N<H)? (wal(L-1,N)+"0") : (wal(L-1,H-(N-H)-1)+"1");
        case 5: return (N<H)? ("0"+wal(L-1,N)) : ("1"+wal(L-1,H-(N-H)-1));
        case 6: return (N<H)? (wal(L-1,N)+"1") : (wal(L-1,H-(N-H)-1)+"0");
        case 7: return (N<H)? ("1"+wal(L-1,N)) : ("0"+wal(L-1,H-(N-H)-1));
    }
    return "error";
}

long long seq(char *s, int i, int j){
    if (i==j) return s[i]-'0';
    long long N = 1LL << (j-i), ret = 0, add = 0;
    switch ((j-i-1)%8){
        case 0 : return (s[j]=='0')? seq(s,i,j-1) : (N + seq(s,i,j-1));
        case 1 : return (s[i]=='0')? seq(s,i+1,j) : (N + seq(s,i+1,j));
        case 2 : return (s[j]=='1')? seq(s,i,j-1) : (N + seq(s,i,j-1));
        case 3 : return (s[i]=='1')? seq(s,i+1,j) : (N + seq(s,i+1,j));
        case 4 : ret = seq(s,i,j-1); if (s[j]=='1') ret = N-ret-1 + N; break;
        case 5 : ret = seq(s,i+1,j); if (s[i]=='1') ret = N-ret-1 + N; break;
        case 6 : ret = seq(s,i,j-1); if (s[j]=='0') ret = N-ret-1 + N; break;
        case 7 : ret = seq(s,i+1,j); if (s[i]=='0') ret = N-ret-1 + N; break;
    }
    return ret;
}

int main(){
    while (scanf("%s",s)!=EOF){
        if (s[0]=='W'){
            scanf("%d %lld",&L,&N);
            printf("%s\n",wal(L, N-1).c_str());
        } else {
            scanf("%s",s);
            printf("%lld\n",seq(s,0,strlen(s)-1)+1);
        }
    }
}

import java.util.*;
import java.io.*;

public class Walaweh {
    String wal(int L, long N){
        if (L==1) return ""+N;
        long H = 1L << (L-1);
        switch ((L-2)%8){
            case 0: return (N<H)? (wal(L-1,N)+"0") : (wal(L-1,N-H)+"1");
            case 1: return (N<H)? ("0"+wal(L-1,N)) : ("1"+wal(L-1,N-H));
            case 2: return (N<H)? (wal(L-1,N)+"1") : (wal(L-1,N-H)+"0");
            case 3: return (N<H)? ("1"+wal(L-1,N)) : ("0"+wal(L-1,N-H));
            case 4: return (N<H)? (wal(L-1,N)+"0") : (wal(L-1,H-(N-H)-1)+"1");
            case 5: return (N<H)? ("0"+wal(L-1,N)) : ("1"+wal(L-1,H-(N-H)-1));
            case 6: return (N<H)? (wal(L-1,N)+"1") : (wal(L-1,H-(N-H)-1)+"0");
            case 7: return (N<H)? ("1"+wal(L-1,N)) : ("0"+wal(L-1,H-(N-H)-1));
        }
        return "error";
    }

    long seq(String S, int i, int j){
        if (i==j) return S.charAt(i)-'0';
        long N = 1L << (j-i), ret = 0, add = 0;
        switch ((j-i-1)%8){
            case 0 : return (S.charAt(j)=='0')? seq(S,i,j-1) : (N + seq(S,i,j-1));
            case 1 : return (S.charAt(i)=='0')? seq(S,i+1,j) : (N + seq(S,i+1,j));
            case 2 : return (S.charAt(j)=='1')? seq(S,i,j-1) : (N + seq(S,i,j-1));
            case 3 : return (S.charAt(i)=='1')? seq(S,i+1,j) : (N + seq(S,i+1,j));
            case 4 : ret = seq(S,i,j-1); if (S.charAt(j)=='1') ret = N-ret-1 + N; break;
            case 5 : ret = seq(S,i+1,j); if (S.charAt(i)=='1') ret = N-ret-1 + N; break;
            case 6 : ret = seq(S,i,j-1); if (S.charAt(j)=='0') ret = N-ret-1 + N; break;
            case 7 : ret = seq(S,i+1,j); if (S.charAt(i)=='0') ret = N-ret-1 + N; break;
        }
        return ret;
    }

    void solve() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (String line; (line = br.readLine())!=null; ){
            String[] s = line.split(" ");
            if (s[0].charAt(0)=='W'){
                int L = Integer.parseInt(s[1]);
                long N = Long.parseLong(s[2]);
                bw.write(wal(L, N-1) + "\n");
            } else {
                bw.write((seq(s[1],0,s[1].length()-1)+1) + "\n");
            }
        }
        br.close();
        bw.close();
    }

    public static void main(String[] args) throws Exception {
        new Walaweh().solve();
    }
}