- #include<bits/stdc++.h>
- using namespace std;
- long long maxnum = 1e10+1;
- vector<vector<int>> cases = {{3,5},{3,7},{5,7}};
- vector<unsigned long long> P_ans;
- unordered_map<unsigned long long,int>mp;
- void cal (){
- for(int i = 0; i<3 ; i++){
- for(int j = 1; j<=20 ; j++){
- for(int k = 1; k<=20; k++){
- unsigned long long p1 = (unsigned long long)pow(cases[i][0],j);
- unsigned long long p2 = (unsigned long long)pow(cases[i][1],k);
- if(mp.find(p1+p2)==mp.end())P_ans.push_back(p1+p2);
- mp[p1+p2] = 1;
- }
- }
- }
- }
- void solve(){
- unsigned long long N , D, I;
- cin>>N>>D>>I;
- sort(P_ans.begin(),P_ans.end());
- long long hi = P_ans.size() , lo = 0, mid = 0;
- while(lo<hi){
- mid = lo +(hi-lo)/2;
- if(P_ans[mid]==N){
- cout<<0<<endl;
- return;
- }
- if(P_ans[mid]<N) {
- lo = mid+1;
- }
- else hi = mid;
- }
- unsigned long long cost = LONG_MAX,cost1,cost2;
- //cout<<lo<<" lo"<<endl;
- if(lo==0){
- if(P_ans[lo]<N){
- cost = min((N-P_ans[lo])*D,cost);
- }
- else {
- cost = min(cost,(P_ans[lo]-N)*I);
- }
- }
- else {
- cost = min((N-P_ans[lo-1])*D,cost);
- if(P_ans[lo]>N){
- cost = min(cost,(P_ans[lo]-N)*I);
- }
- else if(P_ans[lo]<N){
- cost = min(cost,(N-P_ans[lo])*D);
- }
- }
- //cost = cost% (long)(1e9+7);
- cout<<cost<<endl;
- // for(int i = 0;i<P_ans.size();i++){
- // cout<<P_ans[i]<<" ";
- // }
- }
- int main() {
- long t;
- cal();
- cin>>t;
- while(t--) {
- solve();
- }
- return 0;
- }