Mei Ti Le

题目描述

You are given two positive integers $n$ and $k$. Initially, the set is $S=\{1,2,\ldots,n\}.$

You may remove some numbers from $S$. After doing so, you must ensure that for every pair of distinct remaining numbers $x$ and $y$, their sum is not equal to any non-negative integer power of $k$. In other words, there must be no integer $t\ge 0$ such that $x+y=k^t.$

Find the minimum number of elements that must be removed.

You need to answer $T$ independent test cases.

输入格式

The first line contains one integer $T (1\le T\le 10^6)$, the number of test cases.

Each of the next $T$ lines contains two integers $n$ and $k (1\le n,k\le 10^{18})$, describing one test case.

输出格式

For each test case, output one integer on a separate line: the minimum number of elements that must be removed.

样例输入 #1

3
4 1
4 2
4 3

样例输出 #1

0
1
1