[Login|Register]
Problems

Status

Rank

Problem 1286
Verifying CRC polynomial
Time Limit: 1000ms
Memory Limit: 65536kb
Description

Cyclic redundancy check(CRC) is an error-detecting code commonly used many fields.

A common misconception is that the “best” CRC polynomials are derived from either an irreducible polynomial or an irreducible polynomial times the factor (1 + x), which adds to the code the ability to detect all errors affecting an odd number of bits. (Wikipedia)

If you don’t know what I am talking about, please read the web page in above hyperlink.

Given a polynomial of 33 or less bits, please check if it satisfies above condition.

Input

The input consists of multiple test cases. Each test case contains a single string of length n. The (ni)th character indicates the coefficient of xi, and xn’s coefficient is always 1. (2 ≤ n ≤ 32)

The input ends with “0”.

Output

For each test case, output “Case x: ” first, where x is the test case number. Then print “Yes” if above condition holds, or “No” otherwise.

Sample Input
01
0011
1011
00000100110000010001110110110111
0
Sample Output
Case 1: Yes
Case 2: Yes
Case 3: No
Case 4: Yes
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 2.8ms with 1 query(s).