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]