/*------------------------------------------------------------------*/ /*------------------------- begin template -------------------------*/ /*------------------------------------------------------------------*/ // ref: tanakh // diff: using Parser macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut parser = Parser::from_str($s); input_inner!{parser, $($r)*} }; (parser = $parser:ident, $($r:tt)*) => { input_inner!{$parser, $($r)*} }; (new_stdin_parser = $parser:ident, $($r:tt)*) => { let stdin = std::io::stdin(); let reader = std::io::BufReader::new(stdin.lock()); let mut $parser = Parser::new(reader); input_inner!{$parser, $($r)*} }; ($($r:tt)*) => { input!{new_stdin_parser = parser, $($r)*} }; } macro_rules! input_inner { ($parser:ident) => {}; ($parser:ident, ) => {}; ($parser:ident, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($parser, $t); input_inner!{$parser $($r)*} }; } macro_rules! read_value { ($parser:ident, ( $($t:tt),* )) => { ( $(read_value!($parser, $t)),* ) }; ($parser:ident, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($parser, $t)).collect::>() }; ($parser:ident, chars) => { read_value!($parser, String).chars().collect::>() }; ($parser:ident, char_) => { read_value!($parser, String).chars().collect::>()[0] }; ($parser:ident, usize1) => { read_value!($parser, usize) - 1 }; ($parser:ident, i64_) => { $parser.fast_i64() }; ($parser:ident, usize_) => { $parser.fast_i64() as usize }; ($parser:ident, usize1_) => { ($parser.fast_i64() - 1) as usize }; ($parser:ident, $t:ty) => { $parser.next::<$t>().expect("Parse error") }; } use std::io; use std::io::BufRead; use std::str; // ref: tatsuya6502 // ref: wariuni // diff: using std::io::BufRead::fill_buf() pub struct Parser { pub reader: R, buf: Vec, pos: usize, } impl Parser { pub fn from_str(s: &str) -> Parser { Parser { reader: io::empty(), buf: s.as_bytes().to_vec(), pos: 0, } } } impl Parser { pub fn new(reader: R) -> Parser { Parser { reader: reader, buf: vec![], pos: 0, } } pub fn update_buf(&mut self) { self.buf.clear(); self.pos = 0; loop { let (len, complete) = { let buf2 = self.reader.fill_buf().unwrap(); self.buf.extend_from_slice(buf2); let len = buf2.len(); (len, buf2[len - 1] <= 0x20) }; self.reader.consume(len); if complete { break; } } } pub fn next(&mut self) -> Result { loop { let mut begin = self.pos; while begin < self.buf.len() && (self.buf[begin] <= 0x20) { begin += 1; } let mut end = begin; while end < self.buf.len() && (self.buf[end] > 0x20) { end += 1; } if begin != self.buf.len() { self.pos = end; return unsafe { str::from_utf8_unchecked(&self.buf[begin..end]) }.parse::(); } else { self.update_buf(); } } } pub fn fast_i64(&mut self) -> i64 { loop { let mut begin = self.pos; while begin < self.buf.len() && (self.buf[begin] <= 0x20) { begin += 1; } if begin == self.buf.len() { self.update_buf(); continue; } let mut res = 0; let (is_positive, mut end) = match self.buf[begin] { b'+' => (true, begin + 1), b'-' => (false, begin + 1), _ => (true, begin), }; while end < self.buf.len() && (self.buf[end] > 0x20) { res = res * 10 + (self.buf[end] as i64 - '0' as i64); end += 1; } if begin != self.buf.len() { self.pos = end; return if is_positive { res } else { -res }; } else { self.update_buf(); } } } } #[allow(unused_imports)] use std::cmp::*; fn main() { input! { new_stdin_parser = parser, } let res = solve(&mut parser); print!("{}", res); } /*------------------------------------------------------------------*/ /*-------------------------- end template --------------------------*/ /*------------------------------------------------------------------*/ use std::fmt::Write; fn solve(parser: &mut Parser) -> String { let mut buf = String::new(); input! { parser = parser, n: usize, qs: [(i64, i64, i64); n], } for &(a, b, c) in &qs { let mut xs = vec![]; let mut x = a; while x != 0 { xs.push(x % c); x /= c; } xs.reverse(); let mut i = 0; let mut res = b * (xs.len() as i64 - 1); while i < xs.len() { if xs[i] == 0 { i += 1; continue; } if xs[i] == 1 && i + 1 < xs.len() && 0 < xs[i + 1] && xs[i + 1] <= c - 2 { if i == 0 { res += b; } else { res += 2 * b; } i += 2; } else { res += b; i += 1; } } writeln!(buf, "{}", res); } buf }