题目描述

33DAI 最近在研究 IPv6 地址。

IPv6 地址是一个 128 位的数字，它通常表示为 8 组四位十六进制数，每组之间用冒号 : 分隔。为了简化表示，IPv6 地址可以使用以下两种形式的缩写：

1. 省略前导零：每组（16位）中的前导零可以省略。
2. 零压缩：地址中连续的全零段可以用双冒号 :: 替代（在一个地址中只能使用一次）。

现在给定一个保证合法的 IPv6 地址的字符串表示（可能包含上述缩写），请将其完全展开并输出其128位二进制形式。

输入格式

输入包含多组测试数据。

第一行是一个整数 $T$ ($1 \le T \le 10$)，表示测试数据的组数。

接下来 $T$ 行，每行包含一个字符串 $S$（长度不超过 40），代表一个合法的 IPv6 地址。

输出格式

对于每组测试数据，输出一行 $128$ 个 0 或 1 组成的字符串。该字符串是输入 IPv6 地址的128位二进制表示。

3
2001:db8::1428:57ab 
1:2:3:4:5:6:7:8
::1

00100000000000010000110110111000000000000000000000000000000000000000000000000000000000000000000000010100001010000101011110101011
00000000000000010000000000000010000000000000001100000000000001000000000000000101000000000000011000000000000001110000000000001000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001

数据规模与约定

对于所有测试数据，$1 \le T \le 10$。输入的字符串 $S$ 保证是一个合法的 IPv6 地址，只包含十六进制字符 0 ~ 9、a ~ f 和冒号 :。

• 子任务 1：保证没有任何缩写，即保证长度是 $39$。
• 子任务 2：保证没有零压缩。
• 子任务 3：没有特殊性质。