题号：NC219005
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
牛老板(牛牛)是一个土豪，他有无穷数量的纸币，但他的纸币面值很奇怪：
牛老板纸币的面值要么为
，要么为
，其中
%7D)
且
为整数。
牛老板买了一架私人飞机售卖价格为
，牛老板希望在不找零的情况下用尽可能少的纸币付钱，请你帮牛老板计算至少需要多少张纸币。
输入描述:
输入包含
组测试用例，第一行一个整数
接下来
行每行一个整数
输出描述:
输出行，第行为第组测试用例的答案。
示例1
输入
复制
4
6
9
998244353
1000000007
备注:
