2
1000 100
823 821 805 806 801 811 814 815 830 812 807 820 817 803 824 804 819 829 827 813 810 808 816 809 818 826 828 825 822 831 802 852 853 832 862 843 841 858 835 856 837 845 834 852 837 861 854 841 845 833 859 843 834 856 859 850 836 838 833 835 856 857 852 855 834 849 842 862 847 854 848 855 835 839 853 835 850 841 845 840 857 853 856 832 837 861 836 857 857 833 845 846 832 853 841 856 849 849 843 832 823 821 805 806 801 811 814 815 830 812 807 820 817 803 824 804 819 829 827 813 810 808 816 809 818 826 828 825 822 831 802 852 853 832 862 843 841 858 835 856 837 845 834 852 837 861 854 841 845 833 859 843 834 856 859 850 836 838 833 835 856 857 852 855 834 849 842 862 847 854 848 855 835 839 853 835 850 841 845 840 857 853 856 832 837 861 836 857 857 833 845 846 832 853 841 856 849 849 843 832 823 821 805 806 801 811 814 815 830 812 807 820 817 803 824 804 819 829 827 813 810 808 816 809 818 826 828 825 822 831 802 852 853 832 862 843 841 858 835 856 837 845 834 852 837 861 854 841 845 833 859 843 834 856 859 850 836 838 833 835 856 857 852 855 834 849 842 862 847 854 848 855 835 839 853 835 850 841 845 840 857 853 856 832 837 861 836 857 857 833 845 846 832 853 841 856 849 849 843 832 823 821 805 806 801 811 814 815 830 812 807 820 817 803 824 804 819 829 827 813 810 808 816 809 818 826 828 825 822 831 802 852 853 832 862 843 841 858 835 856 837 845 834 852 837 861 854 841 845 833 859 843 834 856 859 850 836 838 833 835 856 857 852 855 834 849 842 862 847 854 848 855 835 839 853 835 850 841 845 840 857 853 856 832 837 861 836 857 857 833 845 846 832 853 841 856 849 849 843 832 823 821 805 806 801 811 814 815 830 812 807 820 817 803 824 804 819 829 827 813 810 808 816 809 818 826 828 825 822 831 802 852 853 832 862 843 841 858 835 856 837 845 834 852 837 861 854 841 845 833 859 843 834 856 859 850 836 838 833 835 856 857 852 855 834 849 842 862 847 854 848 855 835 839 853 835 850 841 845 840 857 853 856 832 837 861 836 857 857 833 845 846 832 853 841 856 849 849 843 832 823 821 805 806 801 811 814 815 830 812 807 820 817 803 824 804 819 829 827 813 810 808 816 809 818 826 828 825 822 831 802 852 853 832 862 843 841 858 835 856 837 845 834 852 837 861 854 841 845 833 859 843 834 856 859 850 836 838 833 835 856 857 852 855 834 849 842 862 847 854 848 855 835 839 853 835 850 841 845 840 857 853 856 832 837 861 836 857 857 833 845 846 832 853 841 856 849 849 843 832 823 821 805 806 801 811 814 815 830 812 807 820 817 803 824 804 819 829 827 813 810 808 816 809 818 826 828 825 822 831 802 852 853 832 862 843 841 858 835 856 837 845 834 852 837 861 854 841 845 833 859 843 834 856 859 850 836 838 833 835 856 857 852 855 834 849 842 862 847 854 848 855 835 839 853 835 850 841 845 840 857 853 856 832 837 861 836 857 857 833 845 846 832 853 841 856 849 849 843 832 823 821 805 806 801 811 814 815 830 812 807 820 817 803 824 804 819 829 827 813 810 808 816 809 818 826 828 825 822 831 802 852 853 832 862 843 841 858 835 856 837 845 834 852 837 861 854 841 845 833 859 843 834 856 859 850 836 838 833 835 856 857 852 855 834 849 842 862 847 854 848 855 835 839 853 835 850 841 845 840 857 853 856 832 837 861 836 857 857 833 845 846 832 853 841 856 849 849 843 832 823 821 805 806 801 811 814 815 830 812 807 820 817 803 824 804 819 829 827 813 810 808 816 809 818 826 828 825 822 831 802 852 853 832 862 843 841 858 835 856 837 845 834 852 837 861 854 841 845 833 859 843 834 856 859 850 836 838 833 835 856 857 852 855 834 849 842 862 847 854 848 855 835 839 853 835 850 841 845 840 857 853 856 832 837 861 836 857 857 833 845 846 832 853 841 856 849 849 843 832 823 821 805 806 801 811 814 815 830 812 807 820 817 803 824 804 819 829 827 813 810 808 816 809 818 826 828 825 822 831 802 852 853 832 862 843 841 858 835 856 837 845 834 852 837 861 854 841 845 833 859 843 834 856 859 850 836 838 833 835 856 857 852 855 834 849 842 862 847 854 848 855 835 839 853 835 850 841 845 840 857 853 856 832 837 861 836 857 857 833 845 846 832 853 841 856 849 849 843 832 
