1006. 合成大 hdu

题目描述

河灵是 hdu 的狂热粉丝。在他眼中，一切的一切都是 hdu 的模样。有一天晚上，河灵在草稿纸上涂鸦时发现，他居然可以在一个字符串中窥见 hdu 的影子！对于一个字符串 S，河灵可以一下子就数出字符串 S 的不同子序列 hdu 的个数。简单的数数已经不能满足河灵了。河灵有一个正整数 n (1 ≤ n ≤ 109)，河灵很想知道拥有不同子序列 hdu 个数恰好为 n 的字符串 S 是什么样的。

,,

请你帮帮河灵，你需要构造一个仅包含 h d u 三种字符的字符串 S，使得字符串 S 的不同子序列 hdu 的个数恰好等于 n。但是河灵的草稿纸大小有限，所以你构造的字符串长度不能超过 3001。可以证明，对于所有满足 1 ≤ n ≤ 109 的正整数 n，至少存在一种满足要求的构造方案。

† 子序列：如果 S ′ 可以通过 S 删除若干个（可能是零个或全部）元素，且不改变剩余元素的相对顺序得到，则称 S ′ 是 S 的子序列。† 不同的子序列：两个子序列 S1, S2 不同，当且仅当原序列中至少存

在一个位置在一个子序列中出现，在另一个子序列中被删除。

输入格式

每个测试点中包含多组测试数据。输入的第一行包含一个正整数 T (

1 ≤ T ≤ 103 )，表示数据组数。对于每组测试数据：一行一个正整数 n (1 ≤ n ≤ 109 )，表示构造的字符串 S 需要包含的不同子序列 hdu 的个数。

输出格式

对于每组测试数据：输出一行一个字符串 S (1 ≤ ∣S∣ ≤ 3001)，表示你构造的字符串。你需要保证字符串 S 仅包含 h, d, u 三种字符。若存在多种满足条件的字符串 S，输出任意一种即可。

样例输入

3
1
3
27

样例输出

hdu
hdhdu
hhhddduuu

来源：官方题面 PDF（2026"钉耙编程"暑期联赛 第2场）