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