Một số được gọi là đối xứng khi viết từ trái sang hoặc từ phải sang không thay đổi giá trị. Một vài số đối xứng đầu tiên: 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, 121, ... (rule 1).

Một vài trường hợp đặc biệt,  0012100, 00 là số đối xứng. Vì vậy 12100, 1210, 00 cũng là số đối xứng (rule 2).

Chúng ta có thể phân loại số nguyên dương thành ba loại:

• Loại 0: là số không phải số đối xứng.
• Loại 1: là những số đối xứng theo rule 1.
• Loại 2: là những số đối xứng theo rule 2.

Tất cả các số đối xứng nhỏ hơn hoặc bằng 100 là 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,  20, 22, 30, 33, 40, 44, 50, 55, 60, 66, 70, 77, 80, 88, 90, 99, 100.

Bạn nhận được số nguyên M không âm. Chức năng của F(M) là trả về số lượng số đối xứng (bao rồi 2 loại: loại 1 và 2) nhỏ hơn hoặc bằng M (0 <= M <= 10³⁵).

Để đơn giản vấn đề, cho một số nguyên N không âm, chức năng cửa P(N) trả về giá trị của F(10^N) (0 <= N <= 35).

Nhiệm vụ

Cho số nguyên dương N, tính P(N).

INPUT

• Dòng đầu tiên chưa số lượng test case 1 <= T <= 36
• T dòng tiếp theo mỗi dòng chứa số nguyên không âm Ni (1 <= i <= T, 0 <= Ni <= 35).

OUTPUT

Kết quả trên T dòng, dòng thứ i chứa giá trị P(Ni) (1 <= i <= T).

Input

3
1
8
10

Output

11
34427
344423