NARYTREE - N-ARY TREE

N-ARY TREE

 

A binary tree is a tree data structure in which each node has at most two child nodes. Similarly an n-ary tree is a data structure in which each node has at most n child nodes.

Given the number of nodes ‘m’ in an ‘n’ary tree, find the minimum possible height of the tree.

 

Input Specification:

The first line consists of an integer t, denoting the number of test cases. Then for the next t lines, each test case consists of two integers ‘m’ and ‘n’ as defined above.

 

Output Specification:

For each test case print the minimum possible height of the tree.

 

Input Constraints: 


1<=t<=100

0<=m<=1000000

1<=n<=1000000


Sample Input:

6

0 5

1 2

8 2

9 2

111 10

112 10


Sample Output:

0

1

4

4

3

4


Added by:cegprakash
Date:2012-05-11
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.