问题 D: Good Tree

内存限制:256 MB 时间限制:2 S
题面:Markdown 评测方式:文本比较 上传者:
提交:5 通过:3

题目描述

Given a tree where all edge weights are $\textstyle 1$, define $\textstyle f(u)=\sum_v dis(u,v)$, where $\textstyle v$ represents all nodes in the tree, and $\textstyle dis(u,v)$ is the length of the simple path between node $\textstyle u$ and node $\textstyle v$. A tree is called “good” if there exist two nodes $\textstyle u$ and $\textstyle v$ such that $\textstyle f(u)-f(v)=x$. Given integer $\textstyle x$, determine the minimum number of nodes required for the tree to be “good”.

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $\textstyle t$ ($\textstyle 1 \leq t \leq 10^5$). The description of the test cases follows. Each test case contains an integer $\textstyle x(1\le x\le 10^{18})$, representing the value for which you need to determine the minimum number of nodes required for the tree to be “good”.

输出格式

For each test case, output a single integer, representing the minimum number of nodes required for the tree to be “good”. It can be shown that the answer always exists.

输入样例 复制

3
2
3
114514

输出样例 复制

4
5
678