A valid Chinese ID card number consists of 17 digits representing region, date, and sequence numbers, plus 1 check digit. The check digit calculation follows these rules:

First, calculate the weighted sum of the first 17 digits using weights: {7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2}. Then compute Z = sum % 11. Finally, map Z to the check digit M using this relationship:

Z: 0 1 2 3 4 5 6 7 8 9 10
M: 1 0 X 9 8 7 6 5 4 3 2

Given a list of ID numbers, your task is to verify the check digit and identify any invalid numbers.

Input Format

The first line contains an integer N (≤100) indicating the number of ID cards. The flolowing N lines each contain one 18-digit ID number.

Output Format

Output each invalid ID number in the order they were received. If all IDs are valid, output "All passed". Note that we only check the check digit validity, not the合理性 of the first 17 digits.

Sample Input 1

4
320124198808240056
12010X198901011234
110108196711301866
37070419881216001X

Sample Output 1

12010X198901011234
110108196711301866
37070419881216001X

Sample Input 2

2
320124198808240056
110108196711301862

Sample Output 2

All passed

Solution Approach

The validation process involves:

1. Reading all ID numbers
2. For each ID, verifying the first 17 characters are digits
3. Calculating the weighted sum of the first 17 digits
4. Determining the expected check digit based on the sum modulo 11
5. Comparing the calculated check digit with the actual 18th character
6. Collecting and reporting invalid IDs

Python Implementation

def validate_id_cards():
    # Define the weight coefficients for the first 17 digits
    weights = [7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2]
    
    # Define the mapping from Z value to check digit
    check_digit_map = ['1', '0', 'X', '9', '8', '7', '6', '5', '4', '3', '2']
    
    # Read number of ID cards
    n = int(input())
    id_cards = [input().strip() for _ in range(n)]
    
    invalid_cards = []
    
    for card in id_cards:
        # Check if first 17 characters are digits
        if not card[:17].isdigit():
            invalid_cards.append(card)
            continue
            
        # Calculate weighted sum of first 17 digits
        total = 0
        for i in range(17):
            total += int(card[i]) * weights[i]
        
        # Calculate Z value (sum modulo 11)
        z_value = total % 11
        
        # Get expected check digit
        expected_check = check_digit_map[z_value]
        
        # Compare with actual check digit (18th character)
        if card[17] != expected_check:
            invalid_cards.append(card)
    
    # Output results
    if not invalid_cards:
        print("All passed")
    else:
        for card in invalid_cards:
            print(card)

if __name__ == "__main__":
    validate_id_cards()

Key Points

• The check digit calculation uses specific weights and mapping
• The 18th character can be 'X' representing the value 10
• We only validate the check digit, not the semantic correctness of the ID
• The solution efficiently processes all IDs and reports invalid ones