All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

Subsequences
/

Algorithms, C++, Combinatorics, Dynamic Programming

Problem
Editorial
Analytics

Your task is to find a range \(L\) to \(R\) (inclusive) such that the number of integers in this range that satisfies the following property is equal to \(K\):

  • Property: Sum of all the subsequences of digits of that number must be odd

For example, 1257 has 1 + 2 + 5 + 7 + 12 + 15 + 17 + 25 + 27 + 57 + 125 + 127 + 257 + 1257 = 1934 as the sum of all subsequences.

Find such a range that is of the minimum length. If more than one such range exists, print the range with the smallest value of \(L\).

Input format

  • The first line contains an integer \(Q\) denoting the number of queries.
  • The next \(Q\) lines contain an integer \(K\).

Output format

For each query, print two integers denoting \(L\) \(R\) in a separate line. If no such range exists, then print -1.

Constraints
\(1 \le Q \le 1e5\\ 1 \le K \le 1e5\)
 

SAMPLE INPUT
2
1
5
SAMPLE OUTPUT
1 1
1 9
Explanation

For Query 1 : 
L = 1 , R = 1 . 1 satisfy given property

For Query 2 :
L = 1 , R = 9 . 1, 3, 5, 7, 9 satisfy given property.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?