数字中没有重复数字的数被称为“单身数”（bachelor numbers）。例如，在十进制系统中，123 是一个单身数；在十六进制系统中，9af 是一个单身数。十进制数 101 和十六进制数 aba 都不是单身数，因为它们包含重复的数字。在本题中，你需要处理两种类型的问题。第一种问题是，给定指定进制（十进制或十六进制）下的一个区间 $[a, b]$，你需要计算该区间内（包含 $a$ 和 $b$）单身数的总数。第二种问题是，给定指定进制下的一个序号 $i$，你需要找到该进制下的第 $i$ 个单身数。

输入格式

输入的第一行是一个整数 $n$，表示测试用例的数量。每个测试用例对应一个问题，占一行。每个问题以字母 ‘d’ 或 ‘h’ 开头，分别表示该问题属于十进制领域或十六进制领域。对于十进制领域，后续数字均以十进制表示。对于十六进制领域，后续数字均以十六进制表示。紧跟在第一个字母后面的是数字 0 或 1，表示问题的类型。对于类型 0 的问题，后面跟着两个整数 $a$ 和 $b$ ($0 \le a \le b < 2^{64}$)，表示一个区间。对于类型 1 的问题，后面跟着一个整数 $1 \le i < 2^{64}$，表示一个序号。

输出格式

对于每个测试用例中的问题，输出一个整数。对于十进制领域的问题，答案必须以十进制输出。对于十六进制领域的问题，答案必须以十六进制输出。对于类型 1 的问题，如果第 $i$ 个单身数不存在，则在该行输出单个字符 ‘-’。

数据范围

• $1 \le n \le 50000$
• $0 \le a \le b < 2^{64}$
• $1 \le i < 2^{64}$

样例

样例输入 1

6
d 0 10 20
h 0 10 1 f
d 1 10
h 1 f
d 1 1000000000
h 1 ffffffffffffffff

样例输出 1

10
f
9
e
-
-