G - 222 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

2,22,222,2222,\ldots という数列があります。この数列の第 i 項は、全ての桁が 2 である i 桁の整数です。

この数列に初めて K の倍数が登場するのは何項目ですか？ 存在しない場合は代わりに -1 と答えてください。

T 個のケースが与えられるので、それぞれについて答えてください。

制約

  • 1 \leq T \leq 200
  • 1 \leq K \leq 10^8
  • 入力に含まれる値は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

各ケースは以下の形式で与えられる。

K

出力

T 行出力せよ。i 行目には \text{case}_i の答えを出力せよ。

入力例 1

4
1
7
10
999983

出力例 1

1
6
-1
999982

4 個のケースが与えられています。

  • 2 は 1 の倍数です
  • 2,22,222,2222,22222 は 7 の倍数ではありませんが、222222 は 7 の倍数です
  • 2,22,\ldots が 10 の倍数になることはありません

Score : 600 points

Problem Statement

We have a sequence 2,22,222,2222,\ldots, where the i-th term is an i-digit integer whose digits are all 2.

Where does a multiple of K appear in this sequence for the first time? If the first multiple of K is the x-th term of the sequence, print x; if there is no multiple of K, print -1.

Given T cases, solve each of them.

Constraints

  • 1 \leq T \leq 200
  • 1 \leq K \leq 10^8
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each case is in the following format:

K

Output

Print T lines. The i-th line should contain the answer for \text{case}_i.

Sample Input 1

4
1
7
10
999983

Sample Output 1

1
6
-1
999982

We have four cases.

  • 2 is a multiple of 1.
  • None of 2,22,222,2222,22222 is a multiple of 7, but 222222 is.
  • None of 2,22,\ldots is a multiple of 10.