The Dirty Path

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Bob is currently at origin. Bob walks only on Xaxis and towards right always. Bob can walk one unit to right, that is from (a,0) to (a+1, 0). Bob can also jump two units to right, that is from (a, 0) to (a+2, 0). However, few coordinates are dirty and Bob does not want to step on those. Bob wants to know the number of ways going to (Y, 0) from (0, 0). Two ways are considered to be different if there exists an integer j such that the location of Bob after j steps is different.
Sounds like a well known problem? Right!! Bob quickly came up with a perfect solution.
A valid path should contain '.' which represent a clean coordinate or '#' which represents a dirty coordinate.
If the length of the path is LEN, then Bob's program calculates and prints number of ways to reach (LEN1, 0) from (0, 0).
An integer X is considered to be a good integer if Bob's program prints X for some valid path.
You have to write a program to output Y, where Y is N^{th} good number in the range L to R. You should also print the valid path that would make Bob's program output Y.
If there are multiple valid paths, you can output any of them. Please see the output section for more details.
Input
The first line of the input contains an integer T denoting the number of test cases.
Only line of each test case contains 3 integers L, R and N.
Output
For each test case, output the N ^{th} good number, followed by space, followed by a valid path. If no such number exists, just output 1.
A valid path should contain '.' which represent a clean coordinate or '#' which represents a dirty coordinate.
For example, "..##.." represents 6 coordinates, (0, 0) (1, 0) .. (5.0) out of which (2, 0) and (3,0) are dirty.
Constraints
 1 ≤ T ≤ 10^5
 0 ≤ L ≤ R ≤ 10^8
 1 ≤ N ≤ 10^5
Example
Input 4 1 3 1 6 9 3 1 3 3 6 9 4 Output 1 . 9 ....#.... 3 .... 1
Explanation
Testcase #1
Good numbers in range [1,3] are 1, 2, 3. 1st of those is 1. There is one way to reach (0, 0) from (0, 0).
Testcase #2
Good numbers in range [6,9] are 6, 8, 9. 3rd of those is 9.
Testcase #4
There are only 3 good numbers in range [6,9].
Author:  anudeep2011 
Tester:  kostya_by 
Editorial  http://discuss.codechef.com/problems/ANUTDP 
Tags  anudeep2011, bfs, binarysearch, cook51, dfs, easymedium, sorting 
Date Added:  26092014 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 