Adler-32 là một hàm băm (hash function) đơn giản, thường được sử dụng để kiểm tra tính toàn vẹn của dữ liệu trong các hệ thống truyền tải dữ liệu và tập tin.

Hàm băm Adler-32 được định nghĩa như sau:

unsigned long adler32(char *data) {
    const unsigned long MOD_ADLER = 65521;
    unsigned long a = 1, b = 0;
    for (int i = 0; data[i] != '\0'; i++) {
        a = (a + (unsigned char)data[i]) % MOD_ADLER;
        b = (b + a) % MOD_ADLER;
    }
    return (b << 16) | a;
}

INPUT

• Dòng 1: Số nguyên dương ~n~.
• ~n~ dòng tiếp theo, mỗi dòng là một chuỗi ký tự có độ dài không quá 100 và không chứa khoảng trắng.

OUTPUT

• In ra một dòng chứa ~n~ giá trị băm Adler-32 tương ứng với mỗi chuỗi, cách nhau bởi dấu cách.

CONSTRAINTS

• ~0 < n \leq 70~

Input

4
toi
khong
biet
gi

Output

44433741 105644568 67436965 20512977