1350 . Nice numbers

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

Description

A “nice number” is a number that starts with some repeating sequences 123456789 and followed by
some additional trailing zeroes:


123456789...1234567890..0



Given a positive integer N, the question is whether there is a multiple of N which is a nice number? For example, for N = 342 we have:


342 * 3609847635188795 = 1234567891234567890



Given an integer N, your task is to write a program that will find the smallest multiple of N which is a
nice number or determine that no such one exists.

Input Format

input file consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 20. The following lines describe the data sets.

Each data set consists of only one line which contains an integer N (1 < N < 106).

Output Format

For each data set, write in one line the smallest multiple of N which is a nice number, or -1 if no such number exists.

Sample Input 1

1
342

Sample Output 1

1234567891234567890

Hints

Problem Source

Migrated from old NTUJ.

The ACM-ICPC 2010 Asia Regional Contest, Site Hanoi

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 6000
Submit
Back to Top