12771277 SUSTech Online Judge
Problem 1277 --K-ary tree

1277: K-ary tree

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 866  Solved: 224
[Submit][Status][Web Board]

Description

Given a complete K-ary tree with N nodes, please find the number of leaf nodes of this tree.
a K-ary tree is a rooted tree where every internal node has at most K child nodes, a K-ary tree of height h is complete if
- Level 0,1,...,h-1 are all full
- At level h, the leaf nodes are as far left as possible.

Input

The first line will be an integer \(T (1 \leq T \leq 1000)\), which is the number of test cases.
For each test data: 
The first line contains two integer N \((2 \leq N \leq 10^8 )\) and K \((2 \leq K \leq 100 )\) — the number of nodes, and the number child nodes it has at most.

Output

For each test cases, print one line with one integer, the number of leaf nodes of this tree

Sample Input

2
5 2
10 3

Sample Output

3
7

HINT

Source

 

[Submit][Status]