You are given n positive integers a 1 , a 2 , ..., a n . For every a i you need to find a positive integer k i such that the decimal notation of 2 k i contains the decimal notation of a i as a substring among its last min (100, length (2 k i )) digits. Here length ( m ) is the length of the decimal notation of m . Note that you don't have to minimize k i . The decimal notations in this problem do not contain leading zeros. The first line contains a single integer n ( 1 ≤ n ≤ 2 000 ) — the number of integers a i . Each of the next n lines contains a positive integer a i ( 1 ≤ a i < 10 11 ). Print n lines. The i -th of them should contain a positive integer k i such that the last min (100, length (2 k i )) digits of 2 k i contain the decimal notation of a i as a substring. Integers k i must satisfy 1 ≤ k i ≤ 10 50 . It can be shown that the answer always exists under the given constraints. If there are multiple answers, print any of them.