提示: 欢迎访问OurACM平台。
Problem 1078 计算循环冗余码

Accept: 477    Submit: 881
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

计算机网络中采用循环冗余码来校验数据的正确性。其原理是:发送方计算出待发送的二进制数据的循环冗余码,并随同原数据一起发送到接收方;接收方通过重新计算接收到的数据的循环冗余码,并和收到的循环冗余码进行比较,如果两者相同则可判定所收到的数据是正确的,否则说明数据是错误的。其中计算二进制数据的循环冗余码的计算过程如下:
1.协议事先约定一个二进制生成表达式,本题设为10011;
2.将待发送的二进制数据串的末尾加4个0;
3.将补上0的数据串按模2除法除于生成表达式,取余数;
4.该余数就是该二进制数据串的循环冗余码。
例如:
数据串为:1101011011
生成表达式为:10011
循环冗余码为:1110
计算过程如下:

根据上述的计算方法,请编写一个循环冗余码计算程序,假设二进制数据串的长度不超过20位,生成表达式固定为10011。

Input

输入的第一行含一个正整数k (1<=k<=10),表示测试例的个数。后面紧接着k行,每行对应一个测试例,含一个N位二进制串(1<=N<=20),代表数据。

Output

每个测试例对应一行输出,含一个5位二进制串,表示循环冗余码。

Sample Input

2 1101011011 10101010

Sample Output

01110 01001

Source

FJNU Preliminary 2005

Submit  Back  Status  Discuss