Description

In the development of "Neural Link" human-computer interface technology, the synchronization signals between the human brain and the computer are encoded as 32-bit unsigned integers (uint32_t). Each bit represents the active state of a micro-neural node, where 1 indicates an active state and 0 indicates a dormant state.

However, due to rejection reactions, the raw received signal $S$ occasionally malfunctions. As a neural engineer, you must write a C firmware program to automatically perform "safety checks" and "neural bridging repair" on the input signal $S$, and calculate the final "checksum signal".

The processing flow must strictly adhere to the following three rules:

Rule 1: Overload Detection

The neural network is extremely fragile, and under no circumstances can two or more "adjacent" neural nodes be active simultaneously (i.e., consecutive 1s).

If the input signal $S$ contains any adjacent 1s (e.g., ...00110... in binary), it must be immediately classified as an overload.

When an overload is detected, your program must output 0xFFFFFFFF directly and ignore all subsequent rules.

Rule 2: Neural Bridging

If the signal passes Rule 1 (no adjacent 1s), you need to stabilize the signal transmission. Energy flows between the "highest active node" and the "lowest active node."

1. Find the Most Significant 1 (MSB) and the Least Significant 1 (LSB) in the signal.
2. To establish a stable neural bridge, you must invert the states (NOT operation) of ALL neural nodes strictly between these two nodes. Bits that were 0 become 1, and bits that were 1 become 0. The MSB and LSB themselves must remain unchanged (1).

Note: If the signal contains only one active node, or no active nodes at all, no inversion is required, and the signal remains unchanged.

The modified signal after this step is referred to as $S_{\text{bridge}}$.

Rule 3: Checksum Integration

To ensure the signal is not tampered with when written back to the brain, $S_{\text{bridge}}$ must undergo a final processing step:

1. Split $S_{\text{bridge}}$ into 4 distinct bytes.
2. Perform a Bitwise XOR operation across these 4 bytes to calculate an 8-bit Checksum.
3. Finally, forcefully replace the lowest byte (Bits 0~7) of $S_{\text{bridge}}$ with this Checksum, while keeping the upper 24 bits unchanged. This represents the final output signal.

Input

The first line contains a positive integer $T$ ($1 \le T \le 4 \times 10^6$), representing the number of test cases.

The following $T$ lines each contain a 32-bit unsigned integer $S$ represented in hexadecimal, prefixed with 0x.

Constraints

• $1 \le T \le 4 \times 10^6$
• $0 \le S \le$ 0xFFFFFFFF
• Please use <stdint.h> and uint32_t to ensure consistent bit-width across different platforms.

Output

For each signal, output the processed 32-bit unsigned integer.

The output must be in hexadecimal format, prefixed with 0x, using uppercase letters, and zero-padded to exactly 8 digits (e.g., 0x0A2B4C6D).

Sample Explanation

• Case 1: 0x00000003 — Binary ends in ...0011. There are adjacent 1s, triggering Rule 1. Output is directly 0xFFFFFFFF.
• Case 2: 0x00000000 — No adjacent 1s. No highest or lowest 1, so Rule 2 does not change the signal ($S_{\text{bridge}} = 0$). For Rule 3, the checksum is 0x00 ^ 0x00 ^ 0x00 ^ 0x00 = 0x00. Replacing the lowest byte yields 0x00000000.
• Case 3: 0x00000008 — Binary is ...1000. No adjacent 1s. Only one 1 (at Bit 3), so no "bits in between". Rule 2 does not change the signal ($S_{\text{bridge}} = \text{0x00000008}$). Checksum is 0x00 ^ 0x00 ^ 0x00 ^ 0x08 = 0x08. Replacing the lowest byte yields 0x00000008.
• Case 4: 0x08000002
  • Rule 1: No adjacent 1s. Passes.
  • Rule 2:
    1. Convert to binary (32 bits): 0000 1000 0000 0000 0000 0000 0000 0010
    2. Find MSB (Most Significant 1): Bit 27; Find LSB (Least Significant 1): Bit 1
    3. Identify the intermediate bits strictly between MSB and LSB: Bit 2 ~ Bit 26 (all currently 0)
    4. Invert all intermediate bits (0 → 1): 0000 1111 1111 1111 1111 1111 1111 1110
    5. Convert back to hex: $S_{\text{bridge}} = \text{0x0FFFFFFE}$
  • Rule 3: Split into bytes: 0x0F, 0xFF, 0xFF, 0xFE. XOR Checksum: 0x0F ^ 0xFF ^ 0xFF ^ 0xFE = 0xF1. Replace lowest byte (0xFE) with 0xF1. Final output: 0x0FFFFFF1.

Sample Input  Download

Sample Output  Download

Tags

Discuss