#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// Function to convert an integer to its binary string representation
string to_binary(int count) {
    string bin = "";
    if(count == 0) return "0";
    while(count > 0){
        bin += (count % 2) ? '1' : '0';
        count /= 2;
    }
    reverse(bin.begin(), bin.end());
    return bin;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;
    
    // Precompute up to K steps
    // K is set to 20, which is sufficient since 2^20 ~ 1e6
    int K = 20;
    
    // To handle all test cases efficiently, we need to find the maximum m across all test cases
    // However, since t can be up to 1e5 and m up to 1e6, storing all test cases first would require too much memory
    // Instead, we'll process test cases on the fly and precompute up to K steps for each m as needed
    
    // To optimize, we'll precompute up to K steps for the first 20 steps
    // and store the last m_max digits for each step
    // However, since m can vary per test case, we'll need a dynamic approach
    
    // Alternative approach:
    // Since m <=1e6 and K=20, we can precompute the last m_max=1e6 digits for each step up to K
    // But storing K=20 strings of size 1e6 is feasible (total memory ~20MB)
    
    // Initialize the first term
    string current = "1";
    
    // Precompute up to K steps, storing only the last m_max digits
    // Since m varies per test case, we'll store all steps up to K
    // and process test cases accordingly
    // To handle m up to 1e6, we'll keep the entire string if it's <=1e6
    // Otherwise, keep only the last 1e6 digits
    // Let's set m_max to 1e6
    const int m_max = 1000000;
    vector<string> steps;
    steps.push_back(current); // step 0: n=1
    
    for(int step=1; step<K; step++){
        string prev = steps.back();
        string next = "";
        int n_prev = prev.size();
        int i=0;
        while(i < n_prev){
            char current_char = prev[i];
            int count = 1;
            while(i+1 < n_prev && prev[i+1] == current_char){
                count++;
                i++;
            }
            // Convert count to binary
            string bin_count = to_binary(count);
            // Append bin_count and the digit
            next += bin_count;
            next += current_char;
            i++;
        }
        // Keep only the last m_max digits
        if(next.size() > m_max){
            next = next.substr(next.size() - m_max, m_max);
        }
        steps.push_back(next);
    }
    
    // Now, process each test case
    while(t--){
        ll n;
        int m;
        cin >> n >> m;
        
        // Determine the step to use
        int step_to_use;
        if(n <= K){
            step_to_use = n-1; // steps[0] corresponds to n=1
        }
        else{
            step_to_use = K-1;
        }
        
        // Get the corresponding term
        string term = steps[step_to_use];
        
        // Check if the term has at least m+1 digits
        if(m >= term.size()){
            cout << "0\n";
        }
        else{
            // Get the m-th digit from the right
            // Rightmost digit has index 0
            char digit = term[term.size() - 1 - m];
            cout << digit << "\n";
        }
    }
}