# 2786. How many digits

Given any integer 0 < = n < = 10000 not divisible by 2 or 5, some multiple of n is a number which in decimal notation is a sequence of 1’s. How many digits are in the smallest such a multiple of n?

### 输入格式

the first line of input gives the number of cases, T(1 < = T < = 50) T cases follow.

Each case contains an integer n.

### 输出格式

Output one line,with the answer described above;

### 样例

Input
3
3
7
9901

Output
3
6
12


96 人解决，116 人已尝试。

121 份提交通过，共有 347 份提交。

3.2 EMB 奖励。