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.

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.

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

2
5 2
10 3

3
7