Untitled

/*
 * Click nbfs://nbhost/SystemFileSystem/Templates/Licenses/license-default.txt to change this license
 * Click nbfs://nbhost/SystemFileSystem/Templates/Classes/Main.java to edit this template
 */
package j01022;

/**
 *
 * @author ntvth
 */
import java.util.*;
public class J01022 {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        Scanner in= new Scanner(System.in);
        int t= Integer.parseInt(in.nextLine());
        int[] F = new int[93];
        F[1]=1;
        F[2]=1;
        for(int i=3;i<93;i++){
            F[i]=F[i-1]+F[i-2];
        }
        while(t-->0){
            int n=Integer.parseInt(in.next());
            int k=Integer.parseInt(in.next());
            while(n>2){
                if(k<=F[n-2]) n-=2;
                else {
                    k-=F[n-2];
                    n-=1;
                }
            }
            if(n==1) System.out.println("0");
            else System.out.println("1");
        }
    }
    
}