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