K-Good Trees | Practice Problems

K-Good Trees

★★★★★

4.4

10 votes

Number Theory, Math, Factorization, Trees, Mathematics, Number theory, Integer Factorization

Details

Submissions

Discussion

Editorial

Problem

Problem:

A tree is called $K-Good (K \geq 1)$ if all the nodes of the tree have exactly $K$ children except the leaves. For given count of leaves $M (M \geq 2)$ , find the number of possible values of $K$ .

Input Format:

The first line of the input contains a single integer $T$ - the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains a single integer $M$ .

Output Format:

For each test case, print the number of possible values of $K$ for given count of leaves $M$ .

Constraints:

$1 \leq T \leq 10^3$
$2 \leq M \leq 10^{9}$

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

Test case $1$ : The possible value of $K$ for $M = 2$ is $2$ .

Test case $2$ : The possible values of $K$ for $M = 3$ are $2$ and $3$ .