Để truy cập mạng WIFI của trường, mỗi học sinh được phát một số nguyên tố ~k~. Với số ~k~ này, học sinh cần tìm số nguyên dương nhỏ nhất ~m~ sao cho tích ~k \times m~ là một số có tất cả các chữ số giống nhau (ví dụ: ~7~, ~11~, ~2222~, ~99999~, …).

Mật khẩu để vào mạng được định nghĩa là phần dư của ~m~ khi chia cho ~10^9+7~.

Toàn trường có ~n~ học sinh, mỗi học sinh có một giá trị ~k~ riêng.

Yêu cầu

Với mỗi ~k~, hãy tìm số nguyên dương nhỏ nhất ~m~ sao cho ~k \times m~ là một số đồng chữ số (mọi chữ số trong hệ thập phân đều bằng nhau).

• Nếu tồn tại, in ra ~m \bmod (10^9+7)~.
• Nếu không tồn tại, in ra ~-1~.

Dữ liệu

• Dòng đầu chứa số nguyên ~n~.
• Mỗi dòng trong ~n~ dòng tiếp theo chứa một số nguyên ~k~.

Kết quả

In ra ~n~ dòng, dòng thứ ~i~ là mật khẩu tương ứng với ~k~ của học sinh thứ ~i~ (hoặc ~-1~ nếu không có lời giải).

Ví dụ

Ví dụ 1

Input

2
11
13

Output

1
8547

Ràng buộc và chấm điểm

• ~1 \le n \le 2000~
• ~1 \le k \le 10^9~
• (Theo mô tả: ~k~ là số nguyên tố)