Chef has recently learned about number bases and is becoming fascinated.
Chef learned that for bases greater than ten, new digit symbols need to be introduced, and that the convention is to use the first few letters of the English alphabet. For example, in base 16, the digits are 0123456789ABCDEF. Chef thought that this is unsustainable; the English alphabet only has 26 letters, so this scheme can only work up to base 36. But this is no problem for Chef, because Chef is very creative and can just invent new digit symbols when she needs them. (Chef is very creative.)
Chef also noticed that in base two, all positive integers start with the digit 1! However, this is the only base where this is true. So naturally, Chef wonders: Given some integer N, how many bases b are there such that the base-b representation of N starts with a 1?

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
Each test case consists of one line containing a single integer N (in base ten).

-----Output-----
For each test case, output a single line containing the number of bases b, or INFINITY if there are an infinite number of them.

-----Constraints-----

-----Subtasks-----Subtask #1 (16 points):
- 1 ≤ T ≤ 103
- 0 ≤ N < 103
Subtask #2 (24 points):
- 1 ≤ T ≤ 103
- 0 ≤ N < 106
Subtask #3 (28 points):
- 1 ≤ T ≤ 103
- 0 ≤ N < 1012
Subtask #4 (32 points):
- 1 ≤ T ≤ 105
- 0 ≤ N < 1012

-----Example-----
Input:4
6
9
11
24

Output:4
7
8
14

-----Explanation-----
In the first test case, 6 has a leading digit 1 in bases 2, 4, 5 and 6: 610 = 1102 = 124 = 115 = 106.

Difficulty: HARD
Tags: Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
import math
t = int(input())
for i in range(t):
	n = int(input())
	if n == 1:
		print('INFINITY')
	else:
		ans = 0
		x = len(bin(n)) - 2
		for j in range(1, x):
			a = math.floor(pow(n / 2, 1 / j))
			b = math.floor(pow(n, 1 / j))
			while 2 * a ** j <= n:
				a += 1
			while 2 * (a - 1) ** j > n:
				a -= 1
			while b ** j > n:
				b -= 1
			while (b + 1) ** j <= n:
				b += 1
			if b - a + 1 > 0:
				ans += b - a + 1
		print(ans)


from math import sqrt as S
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print('INFINITY')
		continue
	else:
		ans = 0
		z = int(S(n))
		for i in range(2, z + 1):
			temp = n
			while temp:
				r = temp % i
				temp = temp // i
			if r == 1:
				ans += 1
		k = n // 2
		if n > k:
			ans += n - k
		print(ans)


from math import ceil, floor
res = []
T = int(input())
for t in range(T):
	N = int(input())
	if N == 1:
		res.append('INFINITY')
		continue
	cnt = 0
	M = (N + 2) // 2
	for i in range(1, 50):
		(n1, m1) = (N ** (1 / i), M ** (1 / i))
		(n, m) = (int(n1), int(m1))
		while (n + 1) ** i <= N:
			n += 1
		while m ** i < M:
			m += 1
		cnt += n - m + 1
	res.append(str(cnt))
print('\n'.join(res))


n = int(input())

def dig(num, b):
	c = 0
	mul = b
	while True:
		if num // mul != 0:
			mul = mul * b
			c += 1
		else:
			break
	return c
for q in range(n):
	num = int(input())
	res = 0
	for i in range(3, num):
		po = dig(num, i)
		if 2 * i ** po - 1 >= num:
			res += 1
	if num == 2:
		res = res + 1
	if num > 2:
		res = res + 2
	if num == 1:
		print('INFINITY')
	else:
		print(res)


def Solve(N):
	if N == 0:
		return 0
	elif N == 1:
		return 'INFINITY'
	elif N == 2:
		return 1
	elif N == 3:
		return 2
	elif N == 4:
		return 3
	elif N > 4:
		count = 0
		(a, b) = (N, N / 2)
		i = 1
		while 1:
			inf = int(pow(b, 1 / i))
			if (inf + 1) ** i <= b:
				inf += 1
			sup = int(pow(a, 1 / i))
			if (sup + 1) ** i <= a:
				sup += 1
			if inf < sup:
				count += sup - inf
			elif sup <= 1:
				break
			i += 1
		return count
for _ in range(int(input())):
	print(Solve(int(input())))


def g(x, k, c):
	t = int(pow((x + 1) / c, 1 / float(k))) + 2
	while c * (t - 1) ** k > x:
		t -= 1
	return t
ncase = int(input())
for testcase in range(ncase):
	x = int(input())
	if x == 0:
		print('0')
	if x == 1:
		print('INFINITY')
	if x > 1:
		ans = 0
		for k in range(1, 40):
			ans += g(x, k, 1) - g(x, k, 2)
		print(ans)


for _ in range(int(input())):
	n = int(input())
	cnt = 0
	for i in range(2, n + 1):
		temp = n
		while temp:
			r = temp % i
			temp = temp // i
		if r == 1:
			cnt += 1
	if n == 1:
		print('INFINITY')
	else:
		print(cnt)


import math
t = int(input())
while t > 0:
	n = int(input())
	if n == 1:
		print('INFINITY')
	elif n == 0:
		print(0)
	else:
		i = 1
		prev_l = 10000000000000.0
		ans = 0
		while True:
			l = math.pow(n / 2, 1 / i)
			r = math.pow(n, 1 / i)
			r = round(r) - 1
			l = round(l) + 1
			if math.pow(r + 1, i) <= n:
				r += 1
			if 2 * math.pow(l - 1, i) > n:
				l -= 1
			ans += r - l + 1
			if l <= 2:
				break
			prev_l = l
			i += 1
		print(ans)
	t -= 1


def finder(n):
	cnt = 0
	for i in range(2, n + 1):
		a = n
		while a != 0:
			r = a % i
			a = a // i
		if r == 1:
			cnt += 1
	return cnt
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 0:
		print(0)
	elif n == 1:
		print('INFINITY')
	else:
		print(finder(n))


t = int(input())
for i in range(0, t):
	n = int(input())
	c = 1
	if n == 0:
		print(0)
	elif n == 1:
		print('INFINITY')
	else:
		for j in range(3, n + 1):
			a = n
			while a >= j:
				a = int(a / j)
			if a == 1:
				c = c + 1
		print(c)


from math import floor, pow, ceil

def goodpow(n, i):
	eps = 5e-06
	x = pow(n, 1 / i)
	y = ceil(x)
	if y - x < eps:
		if pow(y, i) == n:
			return y
	y = floor(x)
	if x - y < eps:
		if pow(y, i) == n:
			return y
	return x
T = int(input())
while T > 0:
	T -= 1
	N = int(input())
	if N == 1:
		print('INFINITY')
		continue
	ans = floor((N + 1) / 2)
	if N % 2 == 0:
		low = ans + 1
	else:
		low = ans
	x = low
	i = 2
	while x >= 2:
		x = goodpow(low, i)
		y = goodpow(N, i)
		ans += floor(y) - floor(x)
		if floor(x) == x:
			ans += 1
		i += 1
	print(ans)


from math import *

def nth_root(val, n):
	ret = int(val ** (1.0 / n))
	return ret + 1 if (ret + 1) ** n == val else ret
for t in range(int(input())):
	n = int(input())
	if n == 1:
		print('INFINITY')
		continue
	ans = (n + 1) // 2
	for x in range(2, 40):
		lower = nth_root((n + 1) // 2, x)
		upper = nth_root(n, x)
		lowerlower = lower ** x
		lowerupper = lowerlower * 2
		upperlower = upper ** x
		upperupper = upperlower * 2
		if not lowerlower <= n < lowerupper:
			lower += 1
		if not upperlower <= n < upperupper:
			upper -= 1
		if upper < lower:
			continue
		if upper < 2:
			break
		ans += upper - lower + 1
	print(ans)


def root(N, k):
	x = int(N ** (1 / k))
	while (x + 1) ** k <= N:
		x += 1
	while x ** k > N:
		x -= 1
	return x
t = int(input())
for i in range(t):
	n = int(input())
	if n == 1:
		print('INFINITY')
	elif n == 2:
		print('1')
	elif n == 0:
		print('0')
	elif n == 3:
		print('2')
	else:
		nn = n // 2
		b = 2
		ans = n - nn + 1
		while root(nn, b) >= 2:
			ans += root(n, b) - root(nn, b)
			b += 1
		print(ans)


def calc(n):
	s = 0
	for i in range(1, int(math.log(n) / math.log(2)) + 1):
		s += int((n + 0.5) ** (1 / i)) - int(((n + 0.2) / 2) ** (1 / i))
	return s

def main(args):
	T = int(input())
	while T:
		T -= 1
		N = int(input())
		if N == 1:
			print('INFINITY')
		elif N == 0:
			print(0)
		else:
			print(calc(N))
	return 0
import sys
import math
sys.exit(main(sys.argv))


import math

def root(x, n):
	ans = int(x ** (1 / n))
	if (ans + 1) ** n == x:
		return ans + 1
	return ans

def ans(N):
	if N == 0 or N == 1:
		print('0' if N == 0 else 'INFINITY')
		return
	res = 0
	dhigh = int(math.log(N, 2))
	d = 1
	while d <= dhigh:
		blow = root(N / 2, d)
		bhigh = root(N, d)
		res += bhigh - blow
		d += 1
	print(res)
tc = int(input())
for i in range(tc):
	n = int(input())
	ans(n)


def ipc(x, t):
	x = abs(x)
	return int(round(x ** (1.0 / t))) ** t == x
for i in range(int(input())):
	n = int(input())
	if n == 1:
		print('INFINITY')
	else:
		s = 0
		for t1 in range(1, 40):
			t = 1 / float(t1)
			b = n / 2.0
			a = n
			if ipc(a, t1):
				a = int(round(a ** (1.0 / t1)))
			else:
				a = int(a ** (1 / t1))
			if ipc(b, t1):
				b = int(round(b ** (1.0 / t1)))
			else:
				b = int(b ** (1 / t1))
			s += int(a) - int(b)
		print(s)


from math import log
from math import floor
from math import ceil

def f1(x, i, n):
	return pow(x, i) - n

def f2(x, i, n):
	return 2 * pow(x, i) - n - 1

def l_search(start, end, i, n):
	while start <= end:
		mid = (start + end) // 2
		if f2(mid + 1, i, n) >= 0 and f2(mid, i, n) < 0:
			return mid + 1
		elif f2(mid, i, n) < 0:
			start = mid + 1
		else:
			end = mid - 1
	return -1

def r_search(start, end, i, n):
	while start <= end:
		mid = (start + end) // 2
		if f1(mid - 1, i, n) < 0 and f1(mid, i, n) >= 0:
			return mid
		elif f1(mid, i, n) < 0:
			start = mid + 1
		else:
			end = mid - 1
	return -1

def max_val(a, i):
	return 2 * pow(a, i) - 1

def min_val(a, i):
	return pow(a, i)
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	if n == 1:
		print('INFINITY')
		continue
	if n == 0:
		print('0')
		continue
	k = floor(log(n, 2)) + 1
	c = 0
	up = n
	for i in range(2, k + 1):
		s = ceil(pow(n, 1 / (i - 1)))
		v = ceil(pow((n - 1) / 2, 1 / (i - 1)))
		up = v + 10
		if s != v:
			c += s - v - 1
		if max_val(s, i - 1) >= n and min_val(s, i - 1) <= n:
			c += 1
		if max_val(v, i - 1) >= n and min_val(v, i - 1) <= n and (s != v):
			c += 1
	print(c)


def f2(N):
	if N == 1:
		return 'INFINITY'
	ans = 0
	i = 1
	while True:
		a1 = int(N ** (1 / i))
		if (a1 + 1) ** i == N:
			a1 = a1 + 1
		a2 = int((N // 2) ** (1 / i))
		if (a2 + 1) ** i == N // 2:
			a2 = a2 + 1
		if a1 <= 1:
			break
		ans = ans + a1 - a2
		i = i + 1
	return ans
for t in range(int(input())):
	print(f2(int(input())))


import math

def nth(n, i):
	x = n ** (1.0 / i)
	x = int(x)
	if (x + 1) ** i <= n:
		return x + 1
	return x
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 0:
		print(0)
		continue
	if n == 1:
		print('INFINITY')
		continue
	if n == 2:
		print(1)
		continue
	c = 0
	m = n // 2
	hip = int(math.log2(n)) + 1
	for i in range(1, hip + 1):
		c += nth(n, i) - nth(m, i)
	print(c)


for _ in range(int(input())):
	n = int(input())
	ans = 0
	if n == 0:
		print(0)
		continue
	if n == 1:
		print('INFINITY')
		continue
	if n == 2:
		print(1)
		continue
	ans = 0
	h = n / 2
	for i in range(1, 45):
		x = int(n ** (1 / i))
		if x ** i > n:
			x -= 1
		elif (x + 1) ** i <= n:
			x += 1
		y = int(h ** (1 / i))
		if y ** i > h:
			y -= 1
		elif (y + 1) ** i <= h:
			y += 1
		ans += abs(x - y)
	print(ans)


for thisniceloop in range(int(input())):
	n = int(input())
	powerflag = 1
	if n == 0:
		print(n)
		continue
	if n == 1:
		print('INFINITY')
		continue
	outputans = 0
	while 1 == 1:
		a = int(pow(n, 1 / powerflag))
		b = int(pow(n / 2, 1 / powerflag))
		if pow(a + 1, powerflag) <= n:
			a += 1
		if pow(b + 1, powerflag) <= n / 2:
			b += 1
		if a == b and b == 1:
			break
		outputans += a - b
		powerflag += 1
	print(outputans)


T = input()
T = int(T)
for a in range(0, T):
	N = input()
	N = int(N)
	unos = 1
	if N == 1:
		print('INFINITY')
	elif N == 0:
		print(0)
	else:
		for b in range(3, N + 1):
			a = N
			while a >= b:
				a = int(a / b)
				if a == 1:
					unos += 1
		print(unos)


import math
num_tests = int(input())
for test_run in range(num_tests):
	ans = 0
	u = 40
	n = int(input())
	if n == 0:
		ans1 = 0
		print(ans1)
	elif n == 1:
		ans1 = 'INFINITY'
		print(ans1)
	else:
		for i in range(1, 40):
			d = ((n + 1) / 2) ** (1.0 / i)
			d = math.floor(d)
			if d ** i < (n + 1) / 2:
				d = d + 1
			if (d - 1) ** i >= (n + 1) / 2:
				d = d - 1
			e = n ** (1.0 / i)
			e = math.floor(e)
			if (e - 1) ** i <= n:
				e = e + 1
			if e ** i > n:
				e = e - 1
			ans = ans + max(0, e - d + 1)
		print(ans)


T = int(input())
for t in range(T):
	N = int(input())
	if N == 1:
		print('INFINITY')
		continue
	cnt = 0
	M = N // 2
	for i in range(1, 50):
		(n1, m1) = (N ** (1 / i), M ** (1 / i))
		(n, m) = (int(n1), int(m1))
		while (n + 1) ** i <= N:
			n += 1
		while (m + 1) ** i <= M:
			m += 1
		cnt += n - m
	print(cnt)


import math
import sys
sys.setrecursionlimit(10 ** 9)

def get(n, l):
	c = int(n ** (1 / l))
	if c ** l == n:
		return c
	elif c ** l < n:
		if (c + 1) ** l <= n:
			return c + 1
		return c
	return c

def get2(n, l):
	k = (n + 1) / 2
	c = int(k ** (1 / l))
	while c ** l < k:
		c += 1
	return c

def ans1(n):
	if n == 0:
		return 0
	elif n == 1:
		return 'INFINITY'
	else:
		l = 1
		a = 0
		while l <= int(math.log2(n)) + 1:
			k1 = get2(n, l)
			k2 = get(n, l)
			a += max(0, k2 - k1 + 1)
			l += 1
		return a
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	print(ans1(n))


import time

def changebase(x, b):
	while x >= b:
		x //= b
	return x
res = []
T = int(input())
st = time.time()
for t in range(T):
	N = int(input())
	if N < 4:
		if N == 0:
			res.append('0')
		elif N == 1:
			res.append('INFINITY')
		elif N == 2:
			res.append('1')
		elif N == 3:
			res.append('2')
		continue
	cnt = 0
	M = N // 2
	i = 1
	en = time.time()
	while True:
		(n, m) = (N ** (1 / i), M ** (1 / i))
		n = round(n) if abs(n - round(n)) < 1e-10 else int(n)
		m = round(m) if abs(m - round(m)) < 1e-10 else int(m)
		if en - st < 9:
			if m < 219:
				break
		elif m < 200:
			break
		cnt += n - m
		i += 1
	cnt += 1
	for i in range(3, n + 1):
		if changebase(N, i) == 1:
			cnt += 1
	res.append(str(cnt))
print('\n'.join(res))


t = eval(input())
for g in range(t):
	n = int(input())
	if n == 0:
		print(0)
	elif n == 1:
		print('INFINITY')
	else:
		a = 0
		for x in range(2, n):
			k = 1
			while n >= x ** k:
				k += 1
			k -= 1
			if 2 * x ** k > n:
				a += 1
		print(a + 1)


for _ in range(int(input())):
	(n, k, p, i) = (int(input()), 0, 1, 9000)
	if n == 1:
		print('INFINITY')
		continue
	while i > 1:
		(i, j) = (int(pow(n + 0.99, 1 / p)), int(pow(n / 2 + 0.49, 1 / p)))
		(k, p) = (k + (i - j), p + 1)
	print(k)


def lb(n, k):
	res = int((n / 2) ** (1 / k))
	if (res + 1) ** k * 2 <= n:
		return res + 1
	else:
		return res

def ub(n, k):
	res = int(n ** (1 / k))
	if (res + 1) ** k <= n:
		return res + 1
	else:
		return res

def test(n, k):
	while n:
		res = n % k
		n //= k
	return res == 1

def raw_cnt(n):
	res = 0
	for i in range(2, n + 1):
		if test(n, i):
			res += 1
	return res

def smart_cnt(n):
	res = 0
	for i in range(1, 100):
		(l, u) = (lb(n, i), ub(n, i))
		res += u - l
		if u == 1:
			break
	return res
T = int(input())
for t in range(T):
	n = int(input())
	if n == 1:
		print('INFINITY')
	else:
		print(smart_cnt(n))


for _ in range(int(input())):
	n = int(input())
	p = 1
	if n == 0:
		print(n)
		continue
	if n == 1:
		print('INFINITY')
		continue
	myfirstintegerns = 0
	while 1 == 1:
		myfirstinteger = int(pow(n, 1 / p))
		b = int(pow(n / 2, 1 / p))
		if (myfirstinteger + 1) ** p <= n:
			myfirstinteger += 1
		if (b + 1) ** p <= n / 2:
			b += 1
		if myfirstinteger == b and b == 1:
			break
		myfirstintegerns += myfirstinteger - b
		p += 1
	print(myfirstintegerns)


import math
cases = int(input())
for _ in range(cases):
	N = int(input())
	if N == 1:
		print('INFINITY')
		continue
	total = 0
	d = 1
	while 1 << d <= N:
		lo = int(math.pow((N + 1) / 2, 1 / d))
		while 2 * pow(lo, d) - 1 < N:
			lo += 1
		hi = int(math.pow(N, 1 / d))
		while pow(hi, d) <= N:
			hi += 1
		hi -= 1
		total += max(0, hi - lo + 1)
		d += 1
	print(total)


import math

def bases(n):
	n = int(n)
	if n == 0:
		return '0'
	elif n == 1:
		return 'INFINITY'
	else:
		sumas = 1
		i = 2
		while i < n:
			arreglo = primer_digito(n, i)
			potencia = arreglo[1]
			primer = arreglo[0]
			resto = n - i ** potencia
			if primer == 1 and potencia == 1:
				sumas += resto
				i += resto
			elif primer == 1:
				sumas += 1
				i += 1
			else:
				i += 1
		return sumas

def primer_digito(numero, base):
	potencia = int(math.log(numero, base))
	primer = numero // base ** potencia
	if primer >= base:
		primer = primer / base
		potencia += 1
	arreglo = [primer, potencia]
	return arreglo
casos = input()
for i in range(int(casos)):
	numero = input()
	print(bases(numero))