Problem D

There is an infinite integer sequence $f_1,f_2,f_3,\dots$, where $f_1=1,f_2=2,f_i=f_{i-1}+f_{i-2}(i\geq 3)$.

You are given two positive integers $n$ and $k$, your task is to check whether $n$ can be split into $k$ integers $a_1,a_2,\dots,a_k$, where $a_1,a_2,\dots,a_k\in f$ and $a_1+a_2+\dots+a_k=n$. Note that you can split $n$ into same integers, for example, $10=5+5=f_4+f_4$.

The first line of the input contains an integer $T(1\leq T\leq 100000)$, denoting the number of test cases.

In each test case, there is one integer $n(1\leq n,k\leq 10^{18})$ in the first line.

For each test case, print a single line. If it is possible to split $n$ into $k$ integers, print Yes, otherwise print No.

4
10 1
10 2
5 1
12 2

No
Yes
Yes
No

"字节跳动杯"杭州电子科技大学第二十届程序设计竞赛