Question 37 Codechef (Game)

Chef has a lightsaber which has an attack power denoted by P$P$. He keeps hitting Darth with the lightsaber. Every time he hits, Darth's health decreases by the current attack power of the lightsaber (by P$P$ points), and afterwards, P$P$ decreases to ⌊P2⌋$\lfloor \frac{P}{2}\rfloor$.

If the attack power becomes 0$0$ before Darth's health becomes 0$0$ or less, Chef dies. Otherwise, Darth dies. You are given Darth's initial health H$H$ and the initial attack power P$P$. Tell Chef if he can beat Darth or if he should escape.

Input

• The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
• The first and only line of each test case contains two space-separated integers H$H$ and P$P$.

Output

For each test case, print a single line containing the integer 1$1$ if Chef can beat Darth or 0$0$ otherwise.

Constraints

• 1≤T≤105$1\le T\le {10}^5$
• 1≤P≤105$1\le P\le {10}^5$
• 1≤H≤106$1\le H\le {10}^6$

Subtasks

Subtask #1 (100 points): original constraints

Example Input

2
10 4
10 8

Example Output

0
1

Solution

def game(h,p):

    h=h-p

    if(h<0):

        h=0

    p=p//2

    return h,p

try:

    t=int(input())

    for i in range(t):

        h,p=map(int,input().split())

        # if(h==1 and p==1):

        #     print(1)

        if(1==1):

            while(h!=0 and p!=0):

                (h,p)=game(h,p)

            if(p==0 and h!=0):

                print(0)

            elif(h==0 and p!=0):

                print(1)

            elif(p==0 and h==0):

                print(1)

except:

    pass