{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"在计算机科学中,Trie或前缀树是一种通常用于存储字符串或数字的数据结构。与二叉树不同,边缘包含字符。一个节点实际上代表了一串字符串,该字符串是通过从根到叶子的路径上取得边缘的字符得到的。例如,对于{abc, ae, bd, bb, bc, abd},我们得到以下Trie:\n\n![Trie](CDN_BASE_URL/f02ff63a7ef237ee2f77aa324d32460c?v\u003d1707138744)\n\n现在给你一组字符串,每个字符串使用**K**个字符符号之一,并且在任何字符串(来自该组)中,一个符号最多出现一次。你的任务是找出使用上述过程制作Trie所需的节点数。由于你不知道集合的大小,因此你的任务是找出最坏情况下的结果。例如,如果你有2个字符符号,则最坏情况下你需要5个节点,如下所示(假设符号为{a, b}):\n\n![Worst Trie with a,b](CDN_BASE_URL/c4230b028bdc8ecf51b7cdec66d334d7?v\u003d1707138744)"}},{"title":"输入","value":{"format":"MD","content":"输入以一个整数**T(≤10000)**开头,表示测试用例的数量。\n\n每个测试用例以包含一个整数**K(1≤K≤10\u003csup\u003e8\u003c/sup\u003e)**的行开始。"}},{"title":"输出","value":{"format":"MD","content":"对于每个测试用例,打印案例编号和最坏情况下所需的总节点数。结果可能很大,如果结果有4位或更多位数,请打印最不重要的4位数字,否则打印结果。"}},{"title":"示例","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n1\n2\n3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 2\nCase 2: 5\nCase 3: 16\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"MD","content":"* 123456789的最不重要的4位数字是6789。"}}]}