p02596 AtCoder Beginner Contest 174 - Repsept_9756
Takahashi loves the number 7 and multiples of K.

Where is the first occurrence of a multiple of K in the sequence 7,77,777,\ldots? (Also see Output and Sample Input/Output below.)

If the sequence contains no multiples of K, print `-1` instead.

Constraints

* 1 \leq K \leq 10^6
* K is an integer.

Input

Input is given from Standard Input in the following format:


K


Output

Print an integer representing the position of the first occurrence of a multiple of K. (For example, if the first occurrence is the fourth element of the sequence, print `4`.)

Examples

Input

101


Output

4


Input

2


Output

-1


Input

999983


Output

999982
K = int(input())
a = 0
ans = -1
for i in range(10**7):
    a = (a*10+7) % K
    if a == 0:
        ans = i+1
        break
print(ans)

2 999983 101 3 1803846 1 1041437 958033 9 172483 2243343 187013 27 62967 57 23239 42117 55133 5041 30689 2849 7083 1929 1533 751 3031 6451 4869 11 199 233 43 177 17 513023 396229 1841409 451457 342119 1208879 1013603 1676603 778149 191049 136963 17097 80531 89 20987 41 42769 173153 107767 20511 31 4983 3711 863 5247 73 51 23 109 229 127 81 53 29 726903 826657 87 139909 316729 19573 908587 13423 21831 9187 52171 126901 71 4231 41797 47 69 919 549 2481 67 179 59 131 141 5513 5163823 1558339 173 439373 6957 86061 5181 204187 11289
-1 999982 4 3
 -1
 1
 245040
 25740
 9
 5032
 747780
 21758
 27
 3450
 18
 10928
 276
 3180
 2485
 15344
 6
 1179
 321
 24
 125
 432
 2150
 540
 2
 99
 232
 21
 174
 16
 18081
 10944
 6138
 220458
 169248
 74010
 1927
 67860
 51876
 15540
 68481
 690
 3660
 44
 5070
 5
 2250
 86154
 96
 819
 15
 150
 618
 862
 234
 8
 48
 22
 108
 228
 42
 81
 13
 28
 342000
 9084
 84
 286
 45246
 1518
 21945
 2160
 3438
 4593
 1792
 6678
 35
 2115
 426
 46
 66
 459
 180
 1239
 33
 178
 58
 130
 138
 444
 73450
 177360
 43
 9802
 1737
 28686
 78
 96080
 1365
