Fenwick Iterations

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef has just learned a new data structure  Fenwick tree. This data structure holds information about array of N elements and can process two types of operations:
 Add some value to i^{th} element of the array
 Calculate sum of all elements on any prefix of the array
Given some array A, first we build data structure in some other array T. T_{i} stores the sum of the elements A_{start}, A_{start + 1}, ..., A_{i}. Index start is calculated with formula start = F_{down}(i) = (i & (i + 1)). Here "&" denotes bitwise AND operation.
So, in order to find a sum of elements A_{0}, A_{1}, ..., A_{L} you start with index L and calculate sum of T_{L} + T_{Fdown(L)1} + T_{Fdown(Fdown(L)1)1} + ... + T_{Fdown(Fdown(...(Fdown(L)1)1)1}. Usually it is performed with cycle that goes from L down to 0 with function F_{down} and sums some elements from T. Chef wants to verify that the time complexity to calculate sum of A_{0}, A_{1}, A_{2}, ..., A_{L} is O(log L). In order to do so, he wonders how many times he has to access array T to calculate this sum. Help him to find this out.
Since Chef works with really big indices. The value of L can be very large and is provided to you in binary representation as concatenation of strings L_{1}, L_{2} repeated N times and string L_{3}.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The only line of each test case contains three nonempty strings L_{1}, L_{2}, L_{3} and an integer N. Strings will contain only characters 0 and 1. To obtain binary representation of index L concatenate L_{1} with L_{2} repeated N times and with L_{3}. You are guaranteed that the index will be positive.
Output
For each test case, output a single line containing number of times Fenwick tree data structure will access array T in order to compute sum of A_{0}, A_{1}, A_{2}, ..., A_{L}.
Constraints
 1 ≤ T ≤ 300
 1 ≤ Length(L_{i}) ≤ 1000
 1 ≤ N ≤ 10^{6}
Subtasks
 Subtask #1 (20 points): L_{1} + L_{2} * N + L_{3} ≤ 60
 Subtask #2 (30 points): 1 ≤ T ≤ 30, 1 ≤ N ≤ 100
 Subtask #3 (50 points): No additional constraints
Example
Input: 4 001 100 011 4 1000 1101 100 3 1010 001 101 4 010 101 000 4 Output: 6 12 8 10
Author:  cenadar 
Tester:  alex_2oo8 
Editorial  http://discuss.codechef.com/problems/FENWITER 
Tags  bit, cenadar, easy, oct16 
Date Added:  16072015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, 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, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions