In Today’s class, Chef is here to teach students about Trees. Tree is a a connected graph of N nodes and N-1 edges.

After class, Chef gave them an assignment to complete. Assignment is as follows :-

Given a tree with single node (root), we need to find whether we can build a tree with exactly N leaf nodes by applying given queries.

Query 1 : Choose any i in between 2 to K and any leaf node say L in current Tree, attach i leaf nodes to L. (We can choose any particular i only once)

Query 2 : Choose an existing edge of Tree and cut the edge. Remove the entire sub-tree attached with that edge.

Students need to answer T independent test cases. Can you help them ?

Example

• If K = 5, N = 6. One possible way to build a tree with N = 6 leaf nodes is :-

o Query 1:1 = 5, leaf node = root. Now, there are 6 nodes in tree and 5 leaf nodes.

o Query 1 : 1 = 2, choose any of the 5 leaf nodes. Now, there are 8 nodes in tree an leaf nodes.

• If K = 2, N = 3. It is not possible to build tree with 3 leaf nodes using given queries.

Function Description

•K: Represents the maximum value of i allowed in Query 1.

•N: Represents the required number of leaf nodes.

Input Format :-

- First line contain an integer T (1<=T <= 105)
- T line consist of two space separated integers K and N

Output Format:

Print 1 if chef can build tree having N-leaf nodes by following queries, otherwise print 0.

Example:

Input:

2

2 3

7 5

Output:

0

1