#include<bits/stdc++.h>
#define int long long
using namespace std;
using ll=long long;
using db=double;
using pii=pair<int,int>;
#define pb push_back
#define endl "\n"
/*
8
4 5 0
5 8 3
9 2 6
15 28 5
97 47 8
164 275 38
114514 1919 810
0 1152921504606846975 1
*/
void solve()
{
    ll x, y, k;
    cin>>x>>y>>k;
    if((!k) || k==1) {cout<<abs(x-y)<<endl;return ;}
    bitset<70>xx(x), yy(y), kk(k);
    int m = 69;
    while(m>=0 && kk[m]==0) m--;
    m++;
    ll d=(y>>m)-(x>>m), ans=0;
    if(d>0){//x<y
        //先变全1
        ll m1=(1ll<<m)-1;
        ll sub=m1^(m1&x);
        if(sub<=k&&sub) ans++;
        else if(sub>k) ans+=2;
        ans++, d--;
        ll bs=0;
        if(k==m1) bs=2;
        else bs=3;
        ans+=bs*d;
        x=0;
    }
    else if(d<0){
        //先全变0
        ll m1=(1ll<<m)-1;
        ll sub=m1&x;
        if(sub<=k&&sub) ans++;
        else if(sub>k) ans+=2;
        ans++, d++;
        ll bs=0;
        if(k==m1) bs=2;
        else bs=3;
        ans-=bs*d;
        x=m1;
    }
    //printf("%lld===\n", ans);
    ll m1=(1ll<<m)-1;
    y = y&m1, x = x&m1;
    ll cost=x^y;
    if(cost<=k&&cost) ans++;
    else if(cost>k) ans+=2;
    cout<< ans <endl;
}

signed main()
{
    #ifdef ONLINE_JUDGE
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    #endif
    int _=1;
    cin>>_;
    while(_--) solve();
    return 0;
}

answer.code: In function ‘void solve()’:
answer.code:62:16: error: no match for ‘operator<’ (operand types are ‘std::basic_ostream<char>::__ostream_type’ {aka ‘std::basic_ostream<char>’} and ‘const char [2]’)
   62 |     cout<< ans <endl;
      |     ~~~~~~~~~~ ^
      |         |
      |         std::basic_ostream<char>::__ostream_type {aka std::basic_ostream<char>}
In file included from /usr/include/c++/13/regex:68,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:181,
                 from answer.code:1:
/usr/include/c++/13/bits/regex.h:1143:5: note: candidate: ‘template<class _BiIter> bool std::__cxx11::operator<(const sub_match<_BiIter>&, const sub_match<_BiIter>&)’
 1143 |     operator<(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/13/bits/regex.h:1143:5: note:   template argument deduction/substitution failed:
answer.code:8:14: note:   ‘std::basic_ostream<char>::__ostream_type’ {aka ‘std::basic_ostream<char>’} is not derived from ‘const std::__cxx11::sub_match<_BiIter>’
    8 | #define endl "\n"
      |              ^~~~
answer.code:62:17: note: in expansion of macro ‘endl’
   62 |     cout<< ans <endl;
      |                 ^~~~
/usr/include/c++/13/bits/regex.h:1224:5: note: candidate: ‘template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator<(__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&, const sub_match<_BiIter>&)’
 1224 |     operator<(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/13/bits/regex.h:1224:5: note:   template argument deduction/substitution failed:
answer.code:8:14: note:   ‘std::basic_ostream<char>::__ostream_type’ {aka ‘std::basic_ostream<char>’} is not derived from ‘std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>’
    8 | #define endl "\n"
      |              ^~~~
answer.code:62:17: note: in expansion of macro ‘endl’
   62 |     cout<< ans <endl;
      |                 ^~~~
/usr/include/c++/13/bits/regex.h:1317:5: note: candidate: ‘template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator<(const sub_match<_BiIter>&, __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&)’
 1317 |     operator<(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/13/bits/regex.h:1317:5: note:   template argument deduction/substitution failed:
answer.code:8:14: note:   ‘std::basic_ostream<char>::__ostream_type’ {aka ‘std::basic_ostream<char>’} is not derived from ‘const std::__cxx11::sub_match<_BiIter>’
    8 | #define endl "\n"
      |              ^~~~
answer.code:62:17: note: in expansion of macro ‘endl’
   62 |     cout<< ans <endl;
      |                 ^~~~
/usr/include/c++/13/bits/regex.h:1391:5: note: candidate: ‘template<class _Bi_iter> bool std::__cxx11::operator<(const typename std::iterator_traits<_Iter>::value_type*, const sub_match<_BiIter>&)’
 1391 |     operator<(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
      |     ^~~~~~~~
/usr/include/c++/13/bits/regex.h:1391:5: note:   template argument deduction/substitution failed:
answer.code:8:14: note:   mismatched types ‘const std::__cxx11::sub_match<_BiIter>’ and ‘const char [2]’
    8 | #define endl "\n"
      |              ^~~~
answer.code:62:17: note: in expansion of macro ‘endl’
   62 |     cout<< ans <endl;
      |                 ^~~~
/usr/include/c++/13/bits/regex.h:1485:5: note: candidate: ‘template<class _Bi_iter> bool std::__cxx11::operator<(const sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type*)’
 1485 |     operator<(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/13/bits/regex.h:1485:5: note:   template argument deduction/substitution failed:
answer.code:8:14: note:   ‘std::basic_ostream<char>::__ostream_type’ {aka ‘std::basic_ostream<char>’} is not derived from ‘const std::__cxx11::sub_match<_BiIter>’
    8 | #define endl "\n"
      |              ^~~~
answer.code:62:17: note: in expansion of macro ‘endl’
   62 |     cout<< ans <endl;
      |                 ^~~~
/usr/include/c++/13/bits/regex.h:1560:5: note: candidate: ‘template<class _Bi_iter> bool std::__cxx11::operator<(const typename std::iterator_traits<_Iter>::value_type&, const sub_match<_BiIter>&)’
 1560 |     operator<(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
      |     ^~~~~~~~
/usr/include/c++/13/bits/regex.h:1560:5: note:   template argument deduction/substitution failed:
answer.code:8:14: note:   mismatched types ‘const std::__cxx11::sub_match<_BiIter>’ and ‘const char [2]’
    8 | #define endl "\n"
      |              ^~~~
answer.code:62:17: note: in expansion of macro ‘endl’
   62 |     cout<< ans <endl;
      |                 ^~~~
/usr/include/c++/13/bits/regex.h:1660:5: note: candidate: ‘template<class _Bi_iter> bool std::__cxx11::operator<(const sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type&...