B'The only difference between easy and hard versions is the maximum value of n . You are given a positive integer number n . You really love good numbers so you want to find the smallest good number greater than or equal to n . The positive integer is called good if it can be represented as a sum of distinct powers of 3 (i.e. no duplicates of powers of 3 are allowed). For example: Note, that there exist other representations of 19 and 20 as sums of powers of 3 but none of them consists of distinct powers of 3 . For the given positive integer n find such smallest m ( n <= m ) that m is a good number. You have to answer q independent queries. The first line of the input contains one integer q ( 1 <= q <= 500 ) -- the number of queries. Then q queries follow. The only line of the query contains one integer n ( 1 <= n <= 10^{18} ). For each query, print such smallest integer m (where n <= m ) that m is a good number. '...