There are N friends who decided to play the game of musical chairs one day.

Initially they decide a number K and with each passing round they remove exactly K chairs. Hence, in each round exactly K players are eliminated. The game stops when less than or exactly K players remain in the game.

Now, Chef wants to figure out for how many possible values of K there will be exactly one winner in the game.

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

- The first line contains T - the number of test cases. Then the test cases follow.
- The first line of each test case contain N - the number of friends in the game.

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

For each test case, output in a single line a integer that denotes the number of values of K for which there will be exactly one winner.

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

$1 ≤ T ≤ 100$
$2 ≤ N ≤ 10^{9}$

----- Sample Input 1 ------ 
3
2
3
4

----- Sample Output 1 ------ 
1
2
2

----- explanation 1 ------ 
- Test case $1$: There will be only one winner if the friends remove exactly $1$ chair each round.
- Test case $2$: There will be only one winner if the friends remove $1$ or $2$ chairs each round. 
- Test case $3$: There will be only one winner if the friends remove $1$ or $3$ chairs each round. If they remove $2$ chairs then there will be two winners.

Difficulty: MEDIUM
Tags: Number theory

Mathematics

Starter code:

Solutions:
import math

def printDivisors(n):
	cnt = 0
	i = 1
	while i <= math.sqrt(n):
		if n % i == 0:
			if n / i == i:
				cnt += 1
			else:
				cnt += 2
		i = i + 1
	return cnt
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(0)
	else:
		print(printDivisors(n - 1))


import math
for i in range(int(input())):
	n = int(input())
	if n == 2:
		print('1')
	else:
		n -= 1
		(cnt, j) = (0, 1)
		while j * j <= n:
			if n % j == 0:
				cnt += 1
				if int(n / j) != j:
					cnt += 1
			j += 1
		print(cnt)


t = int(input())
import math
import time
for _ in range(t):
	n = int(input())
	n -= 1
	c = 0
	for i in range(1, int(math.sqrt(n)) + 1):
		if n % i == 0:
			c += 1
			if n / i != i:
				c += 1
	print(c)


import math
T = int(input())
for i in range(T):
	N = int(input())
	nk = 0
	for K in range(1, int(math.sqrt(N)) + 1):
		if (N - 1) % K == 0:
			nk += 1
			if (N - 1) // K != K:
				nk += 1
	print(nk)


for t in range(int(input())):
	n = int(input())
	i = 1
	ans = 0
	while i * i <= n - 1:
		if (n - 1) % i == 0:
			if i * i < n - 1:
				ans += 2
			elif i * i == n - 1:
				ans += 1
		i += 1
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	x = n - 1
	s = set()
	for i in range(1, int(x ** 0.5) + 1):
		if x % i == 0:
			s.add(i)
			s.add(x // i)
	print(len(s))


import math
for _ in range(int(input())):
	n = int(input())
	ans = 0
	for i in range(1, int(math.sqrt(n - 1)) + 1):
		if (n - 1) % i == 0:
			ans += 1
			if (n - 1) // i != i:
				ans += 1
	print(ans)


import math

def findKValue():
	n = int(input())
	k = 0
	for i in range(1, int(math.sqrt(n - 1)) + 1):
		if (n - 1) % i == 0:
			k += 1
			if (n - 1) // i != i:
				k += 1
	print(k)
for i in range(0, int(input())):
	findKValue()


from math import sqrt, floor
t = int(input())
result = []
for _ in range(t):
	n = int(input())
	x = n - 1
	lim = floor(sqrt(x))
	count = 0
	for k in range(1, lim + 1):
		if x % k == 0:
			count += 1
			if k ** 2 != x:
				count += 1
	result.append(count)
for count in result:
	print(count)


import math
for _ in range(int(input())):
	n = int(input())
	cnt = 0
	s = math.sqrt(n - 1)
	for i in range(1, int(s) + 1):
		if (n - 1) % i == 0:
			v = n // i
			if v == i:
				cnt += 1
			else:
				cnt += 2
	if n == 2:
		print(1)
	else:
		print(cnt)


def totalFactors(N):
	cnt = 0
	for i in range(1, int(N ** 0.5) + 1):
		if N % i == 0:
			cnt += 1
			if i != N / i:
				cnt += 1
	return cnt
for _ in range(int(input())):
	N = int(input())
	print(totalFactors(N - 1))


for t in range(int(input())):
	n = int(input())
	l = 0
	i = 1
	while i * i <= n - 1:
		if (n - 1) % i == 0:
			l += 1
			if (n - 1) // i != i:
				l += 1
		i += 1
	print(l)


import math
tests = int(input())
for i in range(tests):
	num = int(input())
	num -= 1
	ans = 0
	if num == 1:
		ans = 1
	else:
		for j in range(1, math.floor(num ** 0.5) + 1):
			if num % j == 0:
				if num / j == num / (num / j):
					ans += 1
				else:
					ans += 2
	print(ans)


import math
for i in range(int(input())):
	n = int(input())
	n -= 1
	check = False
	ans = 0
	for j in range(1, math.floor(n ** (1 / 2)) + 1):
		if n % j == 0:
			ans += 2
		if j * j == n:
			ans -= 1
	print(ans)


t = int(input())

def factor(n):
	ret = []
	i = 2
	while i * i <= n:
		while n % i == 0:
			ret.append(i)
			n //= i
		i += 1
	if n > 1:
		ret.append(n)
	return ret
for _ in range(t):
	n = int(input())
	hashVal = {}
	ret = factor(n - 1)
	for num in ret:
		if num in hashVal:
			hashVal[num] += 1
		else:
			hashVal[num] = 1
	ans = 1
	for num in hashVal:
		ans *= hashVal[num] + 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	z = n - 1
	l = []
	for i in range(1, int(z ** (1 / 2)) + 1):
		if z % i == 0:
			l.append(i)
			if z // i not in l:
				l.append(z // i)
	print(len(l))


for _ in range(int(input())):
	(n, d, x) = (int(input()) - 1, 1, 0)
	while d * d < n:
		if n % d == 0:
			x += 2
		d += 1
	print(x + (n == d * d))


t = int(input())
for _ in range(t):
	n = int(input())
	x = n - 1
	i = 1
	count = 0
	while i * i <= x:
		if x % i == 0:
			count += 1
			if x // i != i:
				count += 1
		i = i + 1
	print(count)


import math
number_of_test_cases = int(input())
for test in range(0, number_of_test_cases):
	friends = int(input())
	chairs = friends - 1
	possible_chairs_to_remove = 0
	for divisors in range(1, round(math.sqrt(chairs)) + 1):
		if chairs % divisors == 0:
			if divisors ** 2 == chairs:
				possible_chairs_to_remove += 1
			else:
				possible_chairs_to_remove += 2
	print(possible_chairs_to_remove)


def factors(x):
	result = []
	i = 1
	while i * i <= x:
		if x % i == 0:
			result.append(i)
			if x // i != i:
				result.append(x // i)
		i += 1
	return result

def main():
	n = int(input())
	print(len(factors(n - 1)))
for _ in range(int(input())):
	main()


import math
T = int(input())
for _ in range(T):
	n = int(input())
	i = 1
	cnt = 0
	n -= 1
	while i <= math.sqrt(n):
		if n % i == 0:
			if n / i == i:
				cnt += 1
			else:
				cnt += 2
		i = i + 1
	print(cnt)


t = int(input())
for _ in range(0, t):
	n = int(input())
	c = 0
	v = int((n - 1) ** 0.5)
	i = 1
	for i in range(1, v + 1):
		if (n - 1) % i == 0:
			c += 2
	if v * v == n - 1:
		c -= 1
	print(c)


import math
for _ in range(int(input())):
	n = int(input())
	new = n - 1
	count = 0
	if n == 2:
		print(1)
	elif n == 3:
		print(2)
	else:
		for i in range(1, int(math.sqrt(new)) + 1):
			if new % i == 0:
				if i == math.sqrt(new):
					count += 1
				else:
					count += 2
		print(count)


for i in range(int(input())):
	n = int(input()) - 1
	count = 0
	if n == 1:
		print('1')
	elif n == 2:
		print('2')
	else:
		for j in range(1, int(n ** (1 / 2)) + 1):
			if n % j == 0:
				if n ** (1 / 2) == j:
					count += 1
				else:
					count += 2
		print(count)


from math import sqrt
for i in range(int(input())):
	n = int(input())
	a = n - 1
	c = 0
	for j in range(1, int(sqrt(n)) + 1):
		if a % j == 0 and a // j != j:
			c += 2
		elif a % j == 0:
			c += 1
	print(c)


import math
for i in range(int(input())):
	n = int(input())
	c = 0
	for i in range(1, int(math.sqrt(n - 1)) + 1):
		if (n - 1) % i == 0:
			if (n - 1) / i == i:
				c += 1
			else:
				c += 2
	print(c)


from cgi import print_environ
import itertools
import heapq
import collections
import math
from re import M
import sys
from typing import Counter
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def inis():
	return input().split()

def stlt():
	return list(map(str, input().split()))

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	l = []
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			l.append(p)
	return l

def isPrime(n):
	prime_flag = 0
	if n > 1:
		for i in range(2, int(math.sqrt(n)) + 1):
			if n % i == 0:
				prime_flag = 1
				break
		if prime_flag == 0:
			return True
		else:
			return False
	else:
		return False

def gcd(a):
	x = 0
	for p in a:
		x = math.gcd(x, p)
	return x

def printDivisors(n):
	i = 1
	ans = []
	while i <= math.sqrt(n):
		if n % i == 0:
			if n / i == i:
				ans.append(i)
			else:
				ans.append(i)
				ans.append(n // i)
		i = i + 1
	ans.sort()
	return ans

def CountDivisors(n):
	i = 1
	ans = []
	while i <= math.sqrt(n):
		if n % i == 0:
			if n / i == i:
				ans.append(i)
			else:
				ans.append(i)
				ans.append(n // i)
		i = i + 1
	ans.sort()
	return len(ans)

def binaryToDecimal(n):
	return int(n, 2)

def countTriplets(a, n):
	s = set()
	for i in range(n):
		s.add(a[i])
	count = 0
	for i in range(n):
		for j in range(i + 1, n, 1):
			xr = a[i] ^ a[j]
			if xr in s and xr != a[i] and (xr != a[j]):
				count += 1
	return int(count // 3)

def generate_twins(n):
	a = 0
	for i in range(1, n + 1):
		j = i + 2
		if isPrime(i) and isPrime(j):
			if 2 ^ (i ^ j) == 0:
				a += 1
	return a

def smallestDivisor(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n

def countOdd(L, R):
	N = (R - L) // 2
	if R % 2 != 0 or L % 2 != 0:
		N += 1
	return N

def isPalindrome(s):
	return s == s[::-1]
for _ in range(inp()):
	n = inp()
	a = CountDivisors(n - 1)
	print(a)


from math import ceil, sqrt
t = int(input())
while t:
	n = int(input())
	if n == 2:
		print(1)
		t -= 1
		continue
	(count, n) = (0, n - 1)
	for i in range(1, ceil(sqrt(n))):
		if n % i == 0:
			count += 1
	print(count * 2 if int(sqrt(n)) * int(sqrt(n)) != n else count * 2 + 1)
	t -= 1


import math
t = int(input())
for _ in range(t):
	n = int(input())
	count = 0
	n = n - 1
	p = int(math.sqrt(n))
	for i in range(1, p + 1):
		if n % i == 0:
			count += 2
	if p * p == n:
		count -= 1
	print(count)


for s in [*open(0)][1:]:
	s = int(s) - 1
	i = 1
	cnt = 0
	while i <= s ** 0.5:
		if not s % i:
			cnt = cnt + 1 if s / i == i else cnt + 2
		i += 1
	print(cnt)


import math
t = int(input())
for i in range(t):
	n = int(input())
	count1 = 0
	if n == 2:
		print(1)
	else:
		n = n - 1
		for j in range(1, int(math.sqrt(n)) + 1):
			if n % j == 0:
				if n // j == j:
					count1 += 1
				else:
					count1 += 2
		print(count1)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 2:
		print('1')
		continue
	ct = 0
	j = 2
	n -= 1
	while j <= math.sqrt(n):
		if n % j == 0:
			if n / j == j:
				ct += 1
			else:
				ct += 2
		j += 1
	print(ct + 2)


import math
for testcase in range(int(input())):
	n = int(input())
	count = 0
	n = n - 1
	for i in range(1, int(math.sqrt(n)) + 1):
		if n % i == 0:
			if n // i == i:
				count += 1
			else:
				count += 2
	print(count)


import math
t = int(input())
while t > 0:
	N = int(input())
	if N == 2:
		print(1)
	else:
		st = set()
		for i in range(1, int(math.sqrt(N - 1)) + 1):
			if (N - 1) % i == 0:
				st.add(i)
				st.add((N - 1) // i)
		print(len(st))
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	n -= 1
	(counter, i) = (0, 1)
	while i * i <= n:
		if n % i == 0:
			counter += 1
			if i * i != n:
				counter += 1
		i += 1
	print(counter)


import math

def findfact(n):
	cnt = 0
	for i in range(1, int(math.sqrt(n)) + 1):
		if n % i == 0:
			cnt += 1
			if n / i != i and n % (n / i) == 0:
				cnt += 1
	return cnt

def main():
	t = int(input())
	while t > 0:
		n = int(input())
		print(findfact(n - 1))
		t -= 1
main()


try:
	t = int(input())
	for _ in range(t):
		n = int(input())
		n = n - 1
		count = 0
		for i in range(1, int(n ** 0.5) + 1):
			if n % i == 0:
				if n // i == i:
					count += 1
				else:
					count += 2
		print(count)
except:
	pass


from math import *

def factors(x):
	f = 0
	for i in range(1, int(sqrt(x)) + 1):
		if x % i == 0:
			if x // i == i:
				f += 1
			else:
				f += 2
	return f
for _ in range(int(input())):
	print(factors(int(input()) - 1))


for _ in range(int(input())):
	c = 0
	n = int(input())
	n = n - 1
	t = int(n ** 0.5) + 1
	i = 1
	while i < t:
		if n % i == 0:
			if n / i == i:
				c = c + 1
			else:
				c = c + 2
		i += 1
	print(c)


for _ in range(int(input())):
	N = int(input())
	c = 0
	N -= 1
	for i in range(1, int(N ** (1 / 2)) + 1):
		if i * i == N:
			c += 1
		elif N % i == 0:
			c += 2
		else:
			continue
	print(c)


test = int(input())
for a in range(test):
	n = int(input()) - 1
	ans = 0
	i = 1
	sqr = int(n ** 0.5)
	while i <= sqr:
		if n % i == 0:
			ans = ans + 2
		i = i + 1
	if sqr * sqr == n:
		ans = ans - 1
	print(ans)


import sys
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	x = n - 1
	result = []
	i = 1
	while i * i <= x:
		if x % i == 0:
			result.append(i)
			if x // i != i:
				result.append(x // i)
		i += 1
	print(len(result))


from itertools import permutations as per
from math import factorial as fact
from difflib import SequenceMatcher
import bisect

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)
t = int(input())
for _ in range(t):
	n = int(input()) - 1
	ans = 1
	i = 2
	while i * i <= n:
		c = 1
		while n % i == 0:
			c += 1
			n /= i
		ans *= c
		i += 1
	if n > 1:
		ans *= 2
	print(ans)


import math
for i in range(int(input())):
	n = int(input())
	l = 0
	n = n - 1
	for k in range(1, int(math.sqrt(n)) + 1):
		if n % k == 0:
			if k == n // k:
				l += 1
			else:
				l += 2
	print(l)


from math import sqrt
for t in range(int(input())):
	x = int(input())
	count = 0
	n = x - 1
	j = 2
	if x == 2:
		print(1)
	else:
		while j <= sqrt(n):
			if n % j == 0:
				if j * j == n:
					count += 1
				else:
					count += 2
			j += 1
		print(count + 2)


import math
t = int(input())
while t:
	t = t - 1
	k = int(input())
	nk = k - 1
	divisorList = []
	for i in range(1, int(math.sqrt(nk) + 1)):
		if nk % i == 0:
			divisorList.append(i)
			divisorList.append(nk // i)
	divisorList.append(k - 1)
	divisorSet = set(divisorList)
	print(len(divisorSet))


import math

def mgc(x):
	ans = 0
	i = 1
	while i * i <= x:
		if x % i == 0:
			ans += 1
			if i * i != x:
				ans += 1
		i += 1
	return ans
for _ in range(int(input())):
	x = int(input())
	print(mgc(x - 1))


t = int(input())
for _ in range(t):
	n = int(input())
	te = n - 1
	c = 0
	if te == 1:
		c = 1
	else:
		x = int(pow(te, 0.5)) + 1
		for i in range(1, x):
			if te % i == 0:
				c += 1
				if i != te // i:
					c += 1
	print(c)


import math
for _ in range(int(input())):
	n = int(input())
	x = 0
	for i in range(1, int(math.sqrt(n - 1)) + 1):
		if (n - 1) % i == 0:
			if (n - 1) / i == i:
				x += 1
			else:
				x += 2
	print(x)


import math
t = int(input())
while t:
	t -= 1
	n = int(input())
	count = 0
	if n - 1 == 1:
		count += 1
	elif n - 1 == 0:
		pass
	else:
		for i in range(1, int(math.sqrt(n)) + 1):
			p = (n - 1) / i
			if p == int(p):
				if i == p:
					count += 1
				else:
					count += 2
	print(count)


from math import sqrt

def factors(n):
	i = 1
	l = set()
	while i <= sqrt(n):
		if n % i == 0:
			l.add(i)
			l.add(n // i)
		i += 1
	return l
for _ in range(int(input())):
	n = int(input())
	l = factors(n - 1)
	print(len(l))


test = int(input())
for a in range(test):
	n = int(input())
	n = n - 1
	i = 1
	ans = 0
	while i * i <= n:
		if n % i == 0:
			ans = ans + 1
			if i * i != n:
				ans = ans + 1
		i = i + 1
	print(ans)


import math, os, io, heapq
from sys import stdin, stdout
from collections import Counter, deque, defaultdict
from itertools import product
import bisect

def getList(method=int):
	return list(map(method, input().split()))

def getInt():
	return int(input())

def solve():
	n = getInt() - 1
	(fac, i) = (0, 1)
	while i * i <= n:
		if n % i == 0:
			fac += 1 if n // i == i else 2
		i += 1
	return fac
for _ in range(getInt()):
	print(solve())


t = int(input())
for i in range(t):
	n = int(input())
	n -= 1
	c = 0
	for k in range(1, int(n ** 0.5) + 1):
		if n % k == 0:
			if n / k == k:
				c += 1
			else:
				c += 2
	print(c)


import math
t = int(input())
for i in range(t):
	n = int(input())
	cnt = 0
	k = n - 1
	x = math.sqrt(k)
	j = 1
	while j * j <= k:
		if k % j == 0:
			cnt += 1
		j += 1
	if x == k // x:
		print(2 * cnt - 1)
	else:
		print(2 * cnt)


for _ in range(int(input())):
	n = int(input())
	count = 0
	k = 1
	n -= 1
	while k * k <= n:
		if n % k == 0:
			count += 1
			if k * k != n:
				count += 1
		k += 1
	print(count)


from sys import stdin, stdout, maxsize
from math import sqrt, log, factorial as ft, gcd, ceil, floor
from collections import defaultdict
ii = lambda : int(input())
di = lambda : defaultdict(lambda : 0)
dl = lambda : defaultdict(lambda : list())
li = lambda : list(map(int, stdin.readline().strip().split()))
mi = lambda : map(int, stdin.readline().strip().split())
si = lambda : stdin.readline().strip()
for _ in range(ii()):
	n = ii()
	d = di()
	n -= 1
	d[1] = 0
	while n % 2 == 0:
		n //= 2
		d[2] += 1
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0:
			n //= i
			d[i] += 1
		if n == 1:
			break
	if n > 1:
		d[n] += 1
	ans = 1
	for i in d:
		ans *= d[i] + 1
	print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	cnt = 2
	if n == 2:
		print(1)
	else:
		for j in range(2, math.floor(math.sqrt(n - 1)) + 1):
			if (n - 1) % j == 0:
				if j * j == n - 1:
					cnt += 1
				else:
					cnt += 2
			else:
				continue
		print(cnt)


t = int(input())
for _ in range(t):
	n = int(input()) - 1
	cnt = 1
	c = 1
	while n % 2 == 0:
		c += 1
		n = n // 2
	cnt *= c
	for i in range(3, int(n ** 0.5) + 1, 2):
		if n == 1:
			break
		c = 1
		while n % i == 0:
			c += 1
			n = n // i
		cnt *= c
	if n > 2:
		cnt *= 2
	print(cnt)


n = int(input())
for i in range(n):
	x = int(input())
	x -= 1
	count = 0
	j = 1
	while j * j <= x:
		if x % j == 0:
			count += 1
			if j * j != x:
				count += 1
		j += 1
	print(count)


import sys
from collections import deque

def g(l, n, f):
	a = 0
	x = n - 1
	while a <= x:
		m = a + (x - a) // 2
		if l[m] == f:
			return m
		elif l[m] > f:
			x = m - 1
		else:
			a = m + 1
	return None
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	c = 0
	p = int((n - 1) ** (1 / 2))
	if p ** 2 == n - 1:
		c = c - 1
	for i in range(1, int((n - 1) ** 0.5) + 1):
		if (n - 1) % i == 0:
			c = c + 2
	print(c)


t = int(input())
for i in range(t):
	n = int(input())
	c = 0
	n = n - 1
	for j in range(1, int(n ** 0.5) + 1):
		if j * j == n:
			c = c + 1
		elif n % j == 0:
			c = c + 2
		else:
			pass
	print(c)


t = int(input())
for tc in range(t):
	n = int(input())
	n -= 1
	(i, count) = (1, 0)
	while i * i <= n:
		if n % i == 0:
			count += 1
			if i * i != n:
				count += 1
		i += 1
	print(count)


import math
for _ in range(int(input())):
	n = int(input())
	n -= 1
	ans = 0
	for i in range(1, int(math.pow(n, 0.5)) + 1):
		if n % i == 0:
			if n // i == i:
				ans += 1
			else:
				ans += 2
	print(ans)