Read problem statements in [Russian] and [Mandarin Chinese].

A great deal of energy is lost as metabolic heat when the organisms from one trophic level are consumed by the next level. 

Suppose in Chefland the energy reduces by a factor of K, i.e, if initially, the energy is X, then the transfer of energy to the next tropic level is \lfloor \frac{X} {K} \rfloor. This limits the length of foodchain which is defined to be the highest level receiving non-zero energy.

E is the energy at the lowest tropic level. Given E and K for an ecosystem, find the maximum length of foodchain.

Note: \lfloor x \rfloor denoted the floor function, and it returns the greatest integer that is less than or equal to x (i.e  rounds down to the nearest integer). For example, \lfloor 1.4 \rfloor = 1, \lfloor 5 \rfloor = 5, \lfloor -1.5 \rfloor = -2, \lfloor -3 \rfloor = -3 , \lfloor 0 \rfloor = 0.

------ Input Format ------ 

- First line will contain T, number of testcases. Then the testcases follow.
- Each testcase contains a single line of input, two integers E, K.

------ Output Format ------ 

For each testcase, output in a single line answer to the problem.

------ Constraints ------ 

$1 ≤ T ≤ 10^{4}$
$1 ≤ E ≤ 10^{9}$
$2 ≤ K ≤ 10^{9}$

----- Sample Input 1 ------ 
3
5 3
6 7
10 2

----- Sample Output 1 ------ 
2
1
4
----- explanation 1 ------ 
TestCase $1$: The energy at first level is $5$ units. For the second level energy becomes $\lfloor \frac{5} {3} \rfloor = 1$ units. So the length of foodchain is $2$ since from the next level onwards $0$ units of energy will be received.

TestCase $3$: The energy at different levels is:
- Level $1$- $10$ units
- Level $2$- $\lfloor \frac{10} {2} \rfloor = 5$ units
- Level $3$- $\lfloor \frac{5} {2} \rfloor = 2$ units
- Level $4$- $\lfloor \frac{2} {2} \rfloor = 1$ units
- Level $5$- $\lfloor \frac{1} {2} \rfloor = 0$ units

So the answer is $4$, since it is the last level to receive non-zero energy.

Difficulty: EASY
Tags: Constructive algorithms

Implementation

Complete search

Mathematics

Ad-hoc
Skill types: Complete search

Starter code:

Solutions:
for z in range(int(input())):
	(a, b) = map(int, input().split())
	c = 1
	x = 0
	while a // b > 0:
		a = a // b
		c += 1
	print(c)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	c = 1
	while a // b:
		a = a / b
		c += 1
	print(c)


for i in range(int(input())):
	(e, k) = map(int, input().split())
	c = 0
	while e > 0:
		c += 1
		e = int(e / k)
	print(c)


t = int(input())
for i in range(t):
	(e, k) = map(int, input().split())
	count = 0
	while e > 0:
		count += 1
		e = int(e / k)
	print(count)


for i in range(int(input())):
	(E, K) = (int(n) for n in input().split())
	counter = 0
	while E > 0:
		counter += 1
		E = int(E / K)
	print(counter)


cases = int(input())
for _ in range(cases):
	(e, k) = map(int, input().split())
	count = 0
	while e > 0:
		count = count + 1
		e = e // k
	print(count)


import math
n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	c = math.floor(a / b)
	count = 0
	if c <= 0:
		print(1)
		continue
	else:
		while c != 0:
			c = math.floor(a / b)
			a = c
			count += 1
	print(count)


import math
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	c = 0
	while a > 0:
		a = a // b
		c += 1
	print(c)


import math
for i in range(int(input())):
	(n, k) = map(int, input().split())
	c = 0
	while n > 0:
		d = n / k
		e = math.floor(d)
		n = e
		c += 1
	print(c)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	c = 1
	for j in range(a):
		if a // b != 0:
			c += 1
			a = a // b
		else:
			break
	print(c)


t = int(input())
for i in range(t):
	c = 1
	(e, k) = map(int, input().split())
	for i in range(e):
		if e // k != 0:
			e //= k
			c += 1
		else:
			break
	print(c)


for i in range(int(input())):
	(n1, n2) = map(int, input().split())
	c = 1
	while n1 // n2 != 0:
		n1 = n1 // n2
		c = c + 1
	print(c)


t = int(input())
for bunnyy in range(t):
	(e, k) = map(int, input().split())
	a = 0
	while e >= 1:
		e = e // k
		a += 1
	print(a)


for i in range(int(input())):
	(n, x) = map(int, input().split())
	count = 0
	while n >= 1:
		n = n // x
		count += 1
	print(count)


t = int(input())
for i in range(t):
	(x, k) = map(int, input().split())
	count = 0
	a = 0
	while a != 0 or count == 0:
		a = x // k
		count = count + 1
		x = a
	print(count)


import math

def food(a, b):
	c = 0
	while a > 0:
		a = math.floor(a / b)
		c = c + 1
	return c
t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	d = food(a, b)
	print(d)


import math
for turn in range(int(input())):
	(x, k) = map(int, input().split())
	c = 0
	while x > 0:
		x = math.floor(x / k)
		c += 1
	print(c)


for t in range(int(input())):
	(E, K) = map(int, input().split())
	count = 0
	while E > 0:
		count += 1
		E //= K
		pass
	print(count)


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	s = 0
	while a:
		a = a // b
		s += 1
	print(s)


for i in range(0, int(input())):
	list1 = list(map(int, input().split()))
	k = list1[0]
	count = 0
	while k != 0:
		k = k // list1[1]
		count = count + 1
	print(count)


for i in range(int(input())):
	(x, y) = map(int, input().split())
	z = x
	count = 0
	while z != 0:
		z = z // y
		count += 1
	print(count)


import math
for _ in range(int(input())):
	(e, k) = map(int, input().split())
	c = 0
	while e > 0:
		c = c + 1
		e = math.floor(e / k)
	print(c)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	t = True
	ans = 1
	k = int(a / b)
	while k != 0:
		if k > 0:
			ans += 1
			k = int(k / b)
		else:
			k = 0
	print(ans)


import math
for _ in range(int(input())):
	n = list(map(int, input().split()))
	c = 1
	d = 1
	q = n[0]
	while c:
		q = math.floor(q / n[1])
		if q == 0:
			c = c - 1
		else:
			d = d + 1
	print(d)


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	k = 1
	q = a
	while True:
		q = q // b
		if q == 0:
			break
		k += 1
	print(k)


import math
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	count = 1
	a = 1
	while a > 0:
		x = int(x / y)
		if x == 0:
			break
		count += 1
	print(count)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = 0
	while n > 0:
		n = n // k
		a = a + 1
	print(a)


for _ in range(int(input())):
	(e, k) = map(int, input().split())
	s = 0
	while e > 0:
		e = e / k
		s = s + 1
		e = int(e)
	print(s)


for i in range(int(input())):
	(e, k) = list(map(int, input().split()))
	n = 0
	while e > 0:
		e = e // k
		n = n + 1
	print(n)


import math
for r in range(int(input())):
	(e, k) = map(int, input().split())
	c = 1
	x = e / k
	while True:
		if math.floor(x) == 0:
			print(c)
			break
		else:
			c += 1
		x = x / k


import math
for i in range(int(input())):
	(E, K) = map(int, input().split())
	c = 0
	while E > 0:
		c = c + 1
		E = E // K
	print(c)


for _ in range(int(input())):
	(E, K) = map(int, input().split())
	c = 0
	while E != 0:
		E = E // K
		c += 1
	print(c)


h = int(input())
for i in range(h):
	(E, K) = map(int, input().split())
	c = 0
	while E > 0:
		E = E // K
		c = c + 1
	print(c)


t = int(input())
for _ in range(t):
	(e, k) = map(int, input().split())
	c = 0
	while e > 0:
		e = e // k
		c += 1
	print(c)


for _ in range(int(input())):
	(e, k) = map(int, input().split())
	cnt = 1
	while e >= k:
		if e // k > 0:
			cnt += 1
			e = e // k
	print(cnt)


T = int(input())
for i in range(T):
	(E, K) = map(int, input().split())
	count = 1
	while True:
		E = E // K
		if E == 0:
			break
		count += 1
	print(count)


for _ in range(int(input())):
	(f, s) = map(int, input().split())
	energy_level = 1
	for i in range(f):
		f = f // s
		if f != 0:
			energy_level += 1
		else:
			break
	print(energy_level)


T = int(input())
for i in range(T):
	(E, K) = map(int, input().split())
	count = 0
	while E != 0:
		E = E // K
		count += 1
	print(count)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	c = 0
	while a > 0:
		a = a // b
		c += 1
	print(c)


test_cases = int(input())
for _ in range(test_cases):
	(E, K) = input().split()
	E = int(E)
	K = int(K)
	x = E
	count = 0
	while True:
		x = x / K
		count += 1
		if int(x) == 0:
			break
	print(count)


t = int(input())
while t > 0:
	(e, k) = map(int, input().split())
	n = e // k
	c = 1
	while n > 0:
		n = n // k
		c = c + 1
	print(c)
	t = t - 1


for T in range(int(input())):
	(e, k) = map(int, input().split())
	n = 0
	while e > 0:
		n += 1
		e = int(e / k)
	print(n)


for i in range(int(input())):
	(x, y) = map(int, input().split())
	k = 0
	while x != 0:
		k += 1
		x = x // y
	print(k)


tc = int(input())
for _ in range(tc):
	(a, b) = input().split()
	a = int(a)
	b = int(b)
	ans = 0
	while a > 0:
		a = a // b
		ans += 1
	print(ans)


import math
for _ in range(int(input())):
	(e, k) = map(int, input().split())
	print(math.floor(math.log(e, 2) / math.log(k, 2)) + 1)


for _ in range(int(input())):
	(E, K) = map(int, input().split())
	count = 1
	if K > E:
		print(1)
	else:
		E = E // K
		while E > 0:
			count += 1
			E = E // K
		print(count)


t = int(input())
for i in range(t):
	[e, k] = list(map(int, input().split()))
	cnt = 0
	while e != 0:
		e = e // k
		cnt += 1
	print(cnt)


for _ in range(int(input())):
	(e, k) = map(int, input().split())
	count = 1
	for i in range(max(e, k)):
		e = e // k
		if e <= 0:
			break
		else:
			count += 1
	print(count)