Năm 1973, Nhà Toán học Neil Sloan đưa ra khái niệm độ bền của một số nguyên không âm \(N\) như sau:

• Nếu \(N\) có một chữ số thì độ bền bằng 0.
• Gọi \(P(N)\) là tích các chữ số của \(N\), gọi \(D(N)\) là độ bền của số nguyên dương \(N\), khi đó \(D(N)\) được tính: \(D(N)=D(P(N))+1\). Ví dụ: \(D(77)=D(49)+1=D(36)+1+1=D(18)+1+1+1=D(8)+1+1+1+1=0+1+1+1+1=4\).

Yêu cầu:

• Với một số nguyên không âm \(N\) cho trước, bạn hãy ra số nguyên không âm không vượt quá \(N\) có độ bền lớn nhất (nếu có nhiều giá trị thì in ra giá trị nhỏ nhất) và độ bền của số đó.

Input:

• Dòng đầu là một số nguyên dương \(T\) - số lượng testcase \((T≤10000)\).
• \(T\) dòng sau, mỗi dòng gồm một số nguyên không âm \(N (0≤N≤10^{15})\).

Output:

Gồm \(2T\) dòng, mỗi cặp dòng là:

• Dòng đầu là số nguyên dương \(X\) thuộc đoạn \([0,N]\) mà \(D(X)\) lớn nhất.
• Dòng thứ hai là giá trị \(D(X)\).

Example