Để vào mạng WiFi của trường mỗi chú mèo được phát một số nguyên tố k. Với số nguyên tố k được phát muốn vào mạng cần phải tìm số nguyên m nhỏ nhất sao cho k * m làm thành một số có tất cả các chữ số giống nhau. Password vào mạng là phần dư nhận được khi chia m cho 1e9 + 7. Toàn trường có n chú mèo. Hãy xác định password của mỗi chú mèo.

Dữ liệu:

- Dòng đầu là số nguyên n ( n <= 2000)

- Mỗi dòng trong n dòng sau chứa 1 số nguyên tố k ( k <= 2 * 1e9 )

Kết quả: Đưa ra n dòng, mỗi dòng một số là password cần tìm.